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:

  1. Sort all the intervals, based on the starting of intervals.
  2. Create a stack which can hold these intervals; a pair stack.
  3. Now, push the first interval from the set 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 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);
    
}

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

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *