# 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:

- Sort all the intervals, based on the starting of intervals.
- Create a stack which can hold these intervals; a “pair” type stack.
- Now, push the first interval from the set of intervals 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:**

```
/* 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);
}
```

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

**Related Posts:**

- Check whether given Parentheses String are Balanced Parentheses or Not.
- Next Greater Element
- Find Minimum number of bracket reversals required to make an expression balanced.
- Implement Queue Using Two Stacks.
- Implement Stack Using Linked List
- Largest Rectangular Area in Histogram
- Length of Longest Valid Substring
- Reverse a String using Stack
- Implement two stacks in a single array
- Print Bracket Number
- Next Greater Frequency Element
- Sort a Stack using Temporary Stack
- Find Most Frequent Character of the String.
- Check Anagram Strings.
- Check Whether Given String is Palindromic Anagram or Not.
- Check Whether Given String is Panagram or Not.
- Find First Non-Repeating Character of the String.
- Find Most Frequent Element of the Array.
- Find Pair in an Array with Given Sum.
- Find First Repeating Element of an Array.