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

Related Posts:

  1. Implement Stack Using Linked List
  2. Largest Rectangular Area in Histogram
  3. Length of Longest Valid Substring
  4. Reverse a String using Stack
  5. Implement two stacks in a single array
  6. Print Bracket Number
  7. Next Greater Frequency Element
  8. Sort a Stack using Temporary Stack
  9. Infix to Postfix Conversion
  10. Infix to Prefix Conversion
  11. Prefix to Infix Conversion
  12. Prefix to Postfix Conversion
  13. Postfix to Infix Conversion
  14. Postfix to Prefix Conversion
  15. Check whether given Parentheses String are Balanced Parentheses or Not.
  16. Next Greater Element
  17. Find Minimum number of bracket reversals required to make an expression balanced.
  18. Implement Queue Using Two Stacks.
  19. Program to find equilibrium index of an Array.
  20. Program to find majority element of an Array.

You may also like...

Leave a Reply

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