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
Guest
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 Type – Total Number of Guests Present
——————————————————————————————–
1 – Guest arrival/interval start – 1

2 – Guest arrival/interval start – 2

3 – Guest depart/interval end – 1

4 – Guest arrival/interval start – 2

5 – Guest depart/interval end – 1

6 – Guest depart/interval end – 0 //now end the previous non overlapping interval {1,6}

7 – Guest arrival/interval start – 1 i//nitially no of guests were zero so new interval started ie {7,?}

8 – Guest arrival/interval start – 2

8 – Guest depart/interval end – 1

10 – Guest depart/interval end – 0 //now end the previous non overlapping interval {7,10}

12 – Guest arrival/interval start – 1 //initially no of guests were zero so new interval started ie {12,?}

15 – Guest depart/interval end 0 now end the previous non overlapping interval {12,15}

So all non overlapping intervals are {1,6} {7,10} {12,15}

wpDiscuz