Last Updated on October 10, 2022 by Gokul Kannan
Problem Statement
You will be given an array of time intervals that will be in any random order. You have to merge all the overlapping intervals and print only the mutually exclusive intervals i.e. the non-overlapping intervals.
Example
Consider the example shown below.
So, in the above example, {10,30} overlaps with {20,40} since the starting time of interval {20,40} i.e. 20 is not greater than the end time of the interval {10,30}. Hence, we merge them to form the interval {10,40}.
Merge Overlapping Intervals Brute Force Approach
Let us first understand the brute force approach for merging the overlapping intervals. It is straightforward. We will take each interval once and compare it with all the other intervals. If it overlaps with some interval, we merge them. So, in this approach, we are taking an interval out of N intervals and comparing it with the rest N-1 intervals. In the worst case, we will have to do this for all N intervals (no overlapping intervals exist in the worst case). So, the time complexity will be O(N2). Hence, we will not implement (code) this approach. Let us think of something better.
Merge Overlapping Intervals Using Stack
Consider the following intervals shown below.
So, let us try to merge the overlapping intervals in this array. First of all, we will sort the array based on increasing the order of start time as shown below.
Now, we will take an empty stack and push the first interval within the stack.
Now, the next interval is 5-12. Since the start time of the next interval i.e. 5 is less than the end time of the interval present at the top of the stack, this means that these intervals are overlapping. Hence, we have to merge them.
So, we compare the intervals and find out that the end time of the second interval i.e. 12 is greater than the end time of the interval present at the top of the stack. So, we will change the end time of the interval present at the top of the stack to 12 and hence the intervals are merged.
Now, we move to the next interval i.e. 14-19. Here, the start of this interval is greater than the end of the interval present at the top of the stack. So, they are non-overlapping and we will simply add 14-19 to the top of the stack.
We added 14-19 to the top of the stack because we are sure that no interval now will merge with intervals 1-12. This is because the intervals have been sorted concerning their start times and if the start time of the interval 14-19 is not less than the end time of 1-12, the further intervals will have a start time greater than 14 and will not merge with 1-12.
So, the next interval is 22-28. The start time of this interval is also greater than the end time of the interval present at the top of the stack i.e. 22 is greater than 19. So, these are non-overlapping intervals and we will add 22-28 to the top of the stack now.
Next, we have the intervals 25-27. This interval has a start time less than the end time of the interval present at the top of the stack i.e. 25 is less than 28. So, these intervals are overlapping and we will have to merge them.
This time, the end time of the interval at the top of the stack i.e. 28 is greater than the end time of the current interval i.e. 27. So, the current interval will be merged with the top of the stack interval, and will completely be overlapped by the interval at the top of the stack i.e. the end time of the top of the stack will not change as 25-27 lies completely inside 22-28.
Now, the last interval 27-30 is considered. This interval has a start time less than the end time of the interval at the top of the stack. So, merging will take place here as well.
So, the reverse order of the intervals now presents in the stack are non-overlapping intervals in sorted order.
So, this is how we can solve this problem in an optimized approach using Stack and sorting. Now that we have understood this approach, let us write the code for the same.
,Code Implementation
#include <bits/stdc++.h>
using namespace std;
struct Interval {
int start, end;
};
bool compareInterval(Interval i1, Interval i2)
{
return (i1.start < i2.start);
}
void mergeIntervals(Interval arr[], int n)
{
if (n <= 0)
return;
stack<Interval> s;
sort(arr, arr + n, compareInterval);
s.push(arr[0]);
for (int i = 1; i < n; i++) {
Interval top = s.top();
if (top.end < arr[i].start)
s.push(arr[i]);
else if (top.end < arr[i].end) {
top.end = arr[i].end;
s.pop();
s.push(top);
}
}
cout << "\n The Merged Intervals are: ";
while (!s.empty()) {
Interval t = s.top();
cout << "[" << t.start << "," << t.end << "] ";
s.pop();
}
return;
}
int main()
{
Interval arr[]
= { { 1, 8 }, { 5, 12 }, { 14, 19 }, { 22, 28 }, {25, 27} , {27, 30} };
int n = sizeof(arr) / sizeof(arr[0]);
mergeIntervals(arr, n);
return 0;
}
import java.util.*;
public class Main {
public static void mergeIntervals(Interval arr[])
{
if (arr.length <= 0)
return;
Stack<Interval> stack=new Stack<>();
Arrays.sort(arr,new Comparator<Interval>(){
public int compare(Interval i1,Interval i2)
{
return i1.start-i2.start;
}
});
stack.push(arr[0]);
for (int i = 1 ; i < arr.length; i++)
{
Interval top = stack.peek();
if (top.end < arr[i].start)
stack.push(arr[i]);
else if (top.end < arr[i].end)
{
top.end = arr[i].end;
stack.pop();
stack.push(top);
}
}
System.out.print("The Merged Intervals are: ");
while (!stack.isEmpty())
{
Interval t = stack.pop();
System.out.print("["+t.start+","+t.end+"] ");
}
}
public static void main(String args[]) {
Interval arr[]=new Interval[6];
arr[0]=new Interval(1,8);
arr[1]=new Interval(5,12);
arr[2]=new Interval(14,19);
arr[3]=new Interval(22,28);
arr[4]=new Interval(25,27);
arr[5]=new Interval(27,20);
mergeIntervals(arr);
}
}
class Interval
{
int start,end;
Interval(int start, int end)
{
this.start=start;
this.end=end;
}
}
Time Complexity
The time complexity of this approach is O(N LogN) because we are sorting the array first. The time complexity of working with Stack is O(N) but due to sitting the time complexity becomes O(N LogN).
Space Complexity
The space complexity of this approach is O(N) as we are using a stack to solve the problem.
Merge Intervals Space Optimized
So, we saw how we can merge the intervals using stack and sorting. However, if we look carefully, we don’t need a Stack here. We can do the merging in-place without needing a stack as follows.
Except for the first interval, if the current interval overlaps with the previous interval, we merge them and keep doing this till we can merge the intervals.
If the intervals don’t merge, add them to the output array or list.
The code for the above approach is given below.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
struct Interval {
int s, e;
};
bool mycomp(Interval a, Interval b) { return a.s < b.s; }
void mergeIntervals(Interval arr[], int n)
{
sort(arr, arr + n, mycomp);
int index = 0;
for (int i = 1; i < n; i++) {
if (arr[index].e >= arr[i].s) {
arr[index].e = max(arr[index].e, arr[i].e);
}
else {
index++;
arr[index] = arr[i];
}
}
cout << "\n The Merged Intervals are: ";
for (int i = 0; i <= index; i++)
cout << "[" << arr[i].s << ", " << arr[i].e << "] ";
}
int main()
{
Interval arr[]
= { { 1, 8 }, { 5, 12 }, { 14, 19 }, { 22, 28 }, {25, 27} , {27, 30} };
int n = sizeof(arr) / sizeof(arr[0]);
mergeIntervals(arr, n);
return 0;
}
import java.util.*;
class Interval
{
int start,end;
Interval(int start, int end)
{
this.start=start;
this.end=end;
}
}
public class Main {
public static void mergeIntervals(Interval arr[])
{
Arrays.sort(arr,new Comparator<Interval>(){
public int compare(Interval i1,Interval i2)
{
return i1.start - i2.start;
}
});
int index = 0;
for (int i=1; i<arr.length; i++)
{
if (arr[index].end >= arr[i].start)
{
arr[index].end = Math.max(arr[index].end, arr[i].end);
}
else {
index++;
arr[index] = arr[i];
}
}
System.out.print("The Merged Intervals are: ");
for (int i = 0; i <= index; i++)
{
System.out.print("[" + arr[i].start + ","+ arr[i].end + "]\t");
}
}
public static void main(String args[]) {
Interval arr[]=new Interval[6];
arr[0]=new Interval(1,8);
arr[1]=new Interval(5,12);
arr[2]=new Interval(14,19);
arr[3]=new Interval(22,28);
arr[4]=new Interval(25,27);
arr[5]=new Interval(27,20);
mergeIntervals(arr);
}
}
We tried to discuss Merge Overlapping Intervals. We hope this article gives you a better understanding of Merge Overlapping Intervals, PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.