Data Structures Problem 1: Merging Overlapping Intervals
Sorting and arrays are the most frequently asked questions in any software engineering interviews. It is one of the most common problems and also occurs in many natural scenarios. The question is:
Q) Given a collection of intervals, you have to merge all overlapping intervals. For example: Given
[2,6],[5,10],[15,18], return[2,10],[15,18]. Also, mark that the returned intervals list should in non-decreasing order.
The brute force approach
The most common and workable approach is to run 2 loops and check every interval with every other interval and see if they can be merged. But, here the Time Complexity starts from O(n²) which is pretty bad in terms of performance.
An optimised approach
If you look closely into the problem, you can see that if you sort the initial intervals array as per their start time, you will have to traverse the array just once to find all the overlapping intervals. This brings down our Time Complexity to O(nlogn) which is because of the sorting. The following shows the different overlapping cases that can occur.
Overlap case 1:
a---------------------b OR a------b
c-------------------d c----------------dOverlap case 2:
a------------------------b OR a-----------b
c---------d c---------dNon-overlap case :
a-------------------b c------------------dSolution
Sayōnara
