Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we will learn how to solve the Merge Overlapping Intervals problem in most efficient and easy to understand method with the help of stack. We do this in linear time O(N).

Table of contents

Problem statement
General Approach
Algorithm
C++ Implementation
Final Code

Let us get started with Merge Intervals problem. This is similar to Leetcode problem 56. Merge intervals.

Problem Statement

Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals. Intervals are given as input in form of pairs.

Interval is of the form (X_i, Y_i).
This means it covers the time starting from X_i and ending at Y_i.

Sample Input

List of Intervals: (1,3), (2,4), (5,6)

Expected Output

Merged Intervals: (1,4), (5,6)

Note: Intervals (1, 3) and (2, 4) has been merged as (1, 4). These two intervals were merged because the intervals were overlapping.

Prerequiste knowledge

->Do not worry if you are a beginner and stacks and pairs seems difficult to you, these are one of the easiest topics, just go through the article and you will understand the conecpt easily.

General Approach

The steps to merge Intervals are:

Take intervals as input
Store the intervals as vector of pairs of type int
Sort the vector of intervals according to first number in interval and with second number if first number is same.
Use stack to check whether the intervals are overlapping or not by comparing them with elements of vector one by one. The conditions of overlap are:

Consider (a,b) and (c,d) as two intervals

Condition 1 : (a,b) fully overlaps (c,d) where, b>d>c and a<c final interval : (a,b)
Condition 2 : (a,b) partially overlaps (c,d) where, b>c and b<d final interval : (a,d)
Condition 3 : (a,b) does not overlap (c,d) where, b<c<d final intervals : (a,b) and (c,d)

If yes then merge the interval
If no then add the interval as top of stack
At the end final stack will contain merged intervals
Print the output stack

Algorithm

Include header file <bits/stdc++,h>, this header includes most of the header file we will be needing to solve the problem.(Competetive programmers use this too ;))
Take input from user number of pairs of intervals as n
Now to take that input as pairs we will create a vector of pairs like this - vector<pair<int,int>> v
Now run a for loop to take input of pairs and push them in vector v, remember to use ({}) in push_back() beacuse we are taking pair as input. Example - v.push_back({3,6})
Now, sort the vector v, note that sorting will be done according to the first number in every pair which is good, lets see why in next steps
Create a stack using C++ STL(Standard Template Library), push the first element in stack.
Now run a for loop from i=1 to i<n . Create a temp variable of type pair<int,int> and assign stack top to temp which means the first pair in stack is equal to temp.
Main logic to merge- check if upperbound of temp is less than lower bound of next pair of interval, if yes then push next pair into stack.(ex-(1,3) and (4,5) where 3<4 so push (4,5) in stack beacuse no merging can happen here)
Check else if upperbound of temp is less than upperbound of next pair, if yes then this is the condtion to merge the intervals.(ex- (1,3) and (2,4) where 3<4 so merge, push (1,4)
Output the stack elements.

Examples

-> Input :-

{1,4} {2,3} {3,5} {6,7} {7,9}
sort them and add to stack one by one

->iteration 1 :

Stack
(1,4)	top

Stack top is {1,4}.
Compare {1,4} and {2,3}, 4>2 and 4>3 which means {2,3} is subset of {1,4} (complete overlap). So move to next iteration stack top is still {1,4}

->iteration 2 :-

Stack
(1,5)	top

Compare {1,4} with {3,5}, 4<5 so it means {1,4} is overlapping in {3,5} so merge them as {1,5} (partially center overlapped)
Stack top now is {1,5}

->iteration 3 :-

Stack
(6,7)	top
(1,5)

Compare {1,5} with {6,7}, 5<6 so add {6,7} into stack as it is as there is no overlapping between the two intervals.
Stack top is {6,7}

->iteration 4 :-

Stack
(6,9)	top
(1,5)

Compare {6,7} with {7,9}, 7<9 so it is partially right side overlapping so merge them as {6,9}
Stack top is now {6,9}'

->Output :-

{6,9} {1,5}

C++ Implementation

Step 1 : Take input as vector of pairs

     int n;         //number of intervels
     cin>>n;
     vector<pair<int,int>> v;
     for(int i=0;i<n;i++) 
     {              //taking input
       int x,y;
       cin>>x>>y;
       v.push_back({x,y});
     }

Step 2 : Sort the vector and create the stack

     sort(v.begin(),v.end());  
     //sort on the basis of first number in every element
     
     stack<pair<int,int>> s;
     //stack of pairs of type int,int

Step 3 : Run for loop through the vector

Conditions for overlap :

consider (a,b) and (c,d) as two intervals

Condition 1 : (a,b) fully overlaps (c,d)
where, b>d>c and a<c
final interval : (a,b)

Condition 2 : (a,b) partially overlaps (c,d)
where, b>c and b<d
final interval : (a,d)

Condition 3 : (a,b) does not overlap (c,d)
where, b<c<d
final intervals : (a,b) and (c,d)

     s.push(v[0]); // put the first element of vector into the stack
                   // top of stack is now the first element of vector
     
     // run the loop from second element of vector till end
     for(int i=1;i<n;i++)
     { 
       // create a pair to store top pair and compare it with next
       // pairs in vector
       
       pair<int,int> temp = s.top();
       
       // compare with next pair's first element if yes then push
       // that next pair as condition for merging is not met
       // ex- (1,3) and (4,5) , 3<4 so no overlapping no merging
       if(temp.second < v[i].first)
       {
           s.push(v[i]);
       }
       
       // this would be the merging condition because 
       // (1,3) and (2,4) , 3<4 so remove temp from stack and 
       // update temp to merged interval pair and push into stack
    
       else if(temp.second < v[i].second)
       { 
         temp.second=v[i].second;
         s.pop();       //pop old temp value
         s.push(temp);  //push new temp value where interval fixed
       }
       
     }

Step 4 : Output the stack elements

       cout<<"merged intervals are - "<<"\n";
       while(!s.empty())
       {
         pair<int,int> temp= s.top();
         cout<<temp.first<<" "<<temp.second<<"\n";
         
         // pop the pair on top
         s.pop();
         
       }

Time Complexity :

O(nlogn) , because of sorting.

Space Complexity :

O(n) , because of the extra stack to perform stack operations.

Final Code

   #include<bits/stdc++.h>
   using namespace std;
   
   int main()
   { 
     int n;    //number of intervels
     cin>>n;
     vector<pair<int,int>> v;
     for(int i=0;i<n;i++) 
     {//taking input
       int x,y;
       cin>>x>>y;
       v.push_back({x,y});
     }
     
     sort(v.begin(),v.end());  
     //sort on the basis of first number in every element
     
     stack<pair<int,int>> s;
     s.push(v[0]); // do here first eLement

     for(int i=1;i<n;i++)
     {
      
    
       
       pair<int,int> temp = s.top();
       if(temp.second < v[i].first)
       {
           s.push(v[i]);
       }
       else if(temp.second < v[i].second)
       { 
         temp.second=v[i].second;
         s.pop();       //pop old temp value
         s.push(temp);  //push new temp value where interval fixed
       }
       
     }
      cout<<"Merged intervals are :- "<<"\n";
       while(!s.empty())
       {
         pair<int,int> temp= s.top();
         cout<<"("<<temp.first<<","<<temp.second<<")"<<"\n";
         s.pop();
         
       }
       
    
    return 0;
   }

Sample Output

   5 
   6 7
   1 9
   2 6
   8 9
   1 5
   Merged intervals are :- 
   (1,9)

With this article at OpenGenus, you must have the complete idea of Merge Intervals problem.

Merge Intervals problem

Algorithms Stack