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 🙂
 





Leave a Reply

Notify of
avatar
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 present currently become zero end previous interval and start new non overlapping interval eg {1, 5}, {2, 3}, {4, 6}, {7, 8}, {8, 10}, {12, 15} arrays after sorting arr1[] 1,2,4,7,8,12 arr2[] 3,5,6,8,10,15 Initially number of guests is 0 so start a non overlapping interval {1, ?} Time – Event… Read more »
wpDiscuz