×

Search anything:

# Merge Intervals problem

#### Algorithms Stack

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).

1. Problem statement
2. General Approach
3. Algorithm
4. C++ Implementation
5. 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 (Xi, Yi).
This means it covers the time starting from Xi and ending at Yi.

### 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:

1. Take intervals as input
2. Store the intervals as vector of pairs of type int
3. Sort the vector of intervals according to first number in interval and with second number if first number is same.
4. 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)
1. If yes then merge the interval
2. If no then add the interval as top of stack
3. At the end final stack will contain merged intervals
4. Print the output stack

# Algorithm

1. 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 ;))

2. Take input from user number of pairs of intervals as `n`

3. Now to take that input as pairs we will create a vector of pairs like this - `vector<pair<int,int>> v`

4. 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})`

5. 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

6. Create a stack using C++ STL(Standard Template Library), push the first element in stack.

7. 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.

8. 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)

9. 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)

10. 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
``````

## 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