Merging Overlapping Intervals


Given a set of intervals, print all non-overlapping intervals after merging overlapping intervals.

 

For example,


Input:  {1, 5}, {2, 3}, {4, 6}, {7, 8}, {8, 10}, {12, 15}

Intervals after merging overlapping intervals are {1, 6}, {7, 10}, {12, 15}.
 


 
The idea is to sort the intervals in increasing order of their starting time. Then for each interval,

  • If stack is empty or top interval in the stack do not overlap with current interval, we push it to the stack.
     
  • If top interval of stack overlap with current interval, we merge two intervals by updating ending of top interval to ending of current interval.

Finally, we print all non-overlapping intervals present in the stack.

 
C++ implementation –
 

Download   Run Code

Output:

(12, 15)
(7, 10)
(1, 6)

 
The time complexity of above solution is O(nlogn) and auxiliary space used by the program is O(n).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Sort by:   newest | oldest | most voted
Vinayak Sangar
Vinayak Sangar
This problem can be solved in O(nlog n) time and O(1) space as Take two arrays arr1[] array storing the starting index of all the intervals arr2[] array storing the ending indexes of all intervals Now sort both the arrays in ascending order Now every time the number of guests… Read more »
wpDiscuz