# Merge Overlapping Intervals

“** Merge Overlapping Intervals**” is a standard application of stack data structure. Here, we have given set of intervals and our task is to merge all overlapping intervals and then print the resultant non-overlapping intervals.

Example:The set of intervals are: (1,4) , ( 2,5) , (7,8) , ( 6,9). After merging these intervals, the intervals will become (1, 5), (6, 9).

The steps required to merge the overlapping intervals are as follows:

- Sort all the intervals, based on the starting of intervals.
- Create a stack which can hold these intervals; a pair stack.
- Now, push the first interval from the set into the stack.
- For rest of the intervals, if the top interval is merging with current interval, we merge two intervals by updating ending of top interval to ending of current interval.
- Finally, we print the elements of the stack, which are merged intervals.

**C++ Program to Merge Overlapping Intervals Using Stack** **is as follows:**

#include<bits/stdc++.h> using namespace std; void mergeOverlapping(vector< pair<int,int> > &intervals) { // Sort the intervals sort(intervals.begin(), intervals.end()); // Create stack of Interval type stack< pair<int,int> > st; for(int i = 0 ; i < intervals.size() ; i++) { /* If stack is empty, push interval into stack */ if(st.empty()) { st.push(intervals[i]); } /* If Interval is Not Mergeabble */ else if(intervals[i].first > st.top().second) { st.push(intervals[i]); } /* If Interval is Mergeable, merge two intervals by updating ending of top interval to ending of current interval */ else { if(st.top().second < intervals[i].second) { st.top().second = intervals[i].second; } } } // Assign new set of Intervals to Interval Array vector< pair<int,int> > new_Intervals ; while(!st.empty()) { new_Intervals.push_back(st.top()); st.pop(); } reverse(new_Intervals.begin(), new_Intervals.end()); intervals = new_Intervals; } void print(vector< pair<int,int> > intervals) { for(int i = 0 ; i < intervals.size() ; i++) { cout<<intervals[i].first<<" "<<intervals[i].second; cout<<endl; } } int main() { /* 'pair' type vector is used to store the intervals */ vector< pair<int,int> > intervals; // Insert Some Intervals into vector intervals.push_back(make_pair(1,4)); intervals.push_back(make_pair(2,5)); intervals.push_back(make_pair(7,8)); intervals.push_back(make_pair(6,9)); cout<<"The intervals before merging are:\n"; print(intervals); mergeOverlapping(intervals); cout<<"The intervals after merging are:\n"; print(intervals); }

The intervals before merging are: 1 4 2 5 7 8 6 9 The intervals after merging are: 1 5 6 9OUTPUT: