OpenSource 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
anda<c
final interval : (a,b)  Condition 2 : (a,b) partially overlaps (c,d) where,
b>c
andb<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 typepair<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.