# 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 overlapping intervals are as follows:

1. Sort all the intervals, based on the starting of intervals.
2. Create a stack which can hold these intervals; a “pair” type stack.
3. Now, push the first interval from the set of intervals into the stack.
4. 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.
5. Finally, we print the elements of the stack, which are merged intervals.

#### C++ Program to Merge Overlapping Intervals Using Stackis as follows:

```/* Program to Merge Overlapping Intervals Using Stack */
#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);

}

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

Related Posts: