Merge Overlapping Intervals

by · June 9, 2020

“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 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);
    
}


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. Check whether given Parentheses String are Balanced Parentheses or Not.
  2. Next Greater Element
  3. Find Minimum number of bracket reversals required to make an expression balanced.
  4. Implement Queue Using Two Stacks.
  5. Implement Stack Using Linked List
  6. Largest Rectangular Area in Histogram
  7. Length of Longest Valid Substring
  8. Reverse a String using Stack
  9. Implement two stacks in a single array
  10. Print Bracket Number
  11. Next Greater Frequency Element
  12. Sort a Stack using Temporary Stack
  13. Find Most Frequent Character of the String.
  14. Check Anagram Strings.
  15. Check Whether Given String is Palindromic Anagram or Not.
  16. Check Whether Given String is Panagram or Not.
  17. Find First Non-Repeating Character of the String.
  18. Find Most Frequent Element of the Array.
  19. Find Pair in an Array with Given Sum.
  20. Find First Repeating Element of an Array.

Tags:

You may also like...