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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <bits/stdc++.h> using namespace std; // Data structure to represent an interval struct Interval { int begin, end; bool operator<(Interval i) { return (begin < i.begin); } }; // Function to merge overlapping intervals void mergeIntervals(vector<Interval> arr) { // sort the intervals in increasing order of their starting time sort(arr.begin(), arr.end()); // create an empty stack stack<Interval> stk; // do for each interval for (Interval curr: arr) { // if stack is empty or top interval in stack do not overlap // with current interval, push it to the stack if (stk.empty() || curr.begin > stk.top().end) stk.push(curr); // if top interval of stack overlap with current interval, // merge two intervals by updating ending of top interval // to ending of current interval if (stk.top().end < curr.end) stk.top().end = curr.end; } // print all non-overlapping intervals while (!stk.empty()) { cout << "(" << stk.top().begin << ", " << stk.top().end << ")\n"; stk.pop(); } } // main function int main() { vector<Interval> arr = { { 1, 5 }, { 2, 3 }, { 4, 6 }, { 7, 8 }, { 8, 10 }, {12, 15} }; mergeIntervals(arr); return 0; } |

**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

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}