An interval is a set of real numbers lying between any two numbers.
For example, If the starting point of the interval is “a” and the ending point is “b,” then we denote the interval as [a,b]. Two intervals [a,b] and [c,d] are mutually exclusive, if a<=b<c<=d or c<=d<a<=b. So basically, for being mutually exclusive, the two intervals should not have any part of them overlapping with each other.
In this article, we’ll see how to solve the problem- Merge Intervals frequently asked in Amazon, Microsoft and many product-based companies.
Problem Statement
You are given N number of intervals, where each interval contains two integers denoting the start time and the end time for the interval.
The task is to merge all the overlapping intervals and return the list of merged intervals sorted by increasing order of their start time
Two intervals [A,B] and [C,D] are said to be overlapping with each other if there is at least one integer that is covered by both of them.
A simple approach is to first sort the intervals according to their starting point. Then, start from the first interval and compare it with its next interval to check if they are overlapping or not.
If yes, then merge them into one and erase the later interval. Do the same step for each of the other intervals.
We will be erasing here using the vector erase v.erase() function.
The steps are as follows :
Sort the intervals according to their starting time.
Start from i=0 and compare the interval here with the next interval. Do the same for each i<intervals.size()-1.
For comparing:
If the start time of the interval[i+1] is greater than the end time of interval[i], then they don’t overlap. So just move on to the next i.
Otherwise, if they overlap, check if the end of (i)th interval is greater than the end of the (i+1)th interval. If yes, then the (i+1)th interval lies completely inside the ith interval so we need to delete it. If not, we need to update the end of the ith interval equal to the end of the (i+1)th interval, and then delete the (i+1)th interval
Let’s see the implementation of the above approach.
#include<bits/stdc++.h> usingnamespace std;
voidcompare(int &i, vector<int> &vi, vector<int> &v_next, vector<vector<int>>& intervals) { int s1 = vi[0]; //start of ith interval int e1 = vi[1]; // end of ith interval int s2 = v_next[0]; //start of the (i+1)th interval int e2 = v_next[1]; // end of the (i+1)th interval if (e1 >= s2) { //if the start of (i+1)th interval is smaller than the //end of the ith interval, the intervals are overlapping if (e1 > e2) { //if the end of (i)th interval is greater than the //end of the (i+1)th interval, then the (i+1) interval lies completely inside // the ith interval so we need to delete it. intervals.erase(intervals.begin()+i+1); // O(n) } else{ //Otherwise, we need to update the end of the ith interval equal to end of the // (i+1)th interval, and then delete the (i+1)th interval vi[1] = v_next[1]; intervals.erase(intervals.begin()+i+1); } } else//Otherwise, the intervals aren't overlapping, so just move on to the next i. i++; }
vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end()); // O(nlogn) int i=0; while(i<intervals.size()-1) { //O(n^2) compare(i, intervals[i], intervals[i+1], intervals); // compare the two consecutive intervals } return intervals; }
intmain(){ int n; // number of intervals cin>>n; vector<vector<int>>intervals(n); //vector for storing all the intervals for(int i=0;i<n;i++){ int start,end; cin>>start>>end; // start and end time of all the intervals intervals[i].push_back(start); intervals[i].push_back(end); } vector<vector<int>>ans = merge(intervals); // vector for storing all the //mutually exclusive intervals //Printing ans for(auto x:ans){ for(auto y:x){ cout<<y<<" "; } cout<<endl; } return0; }
Input
n=4 , intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]
Complexity Analysis
Time Complexity
O(n^2), where n is the number of intervals.
Reason: Since sorting takes O(nlogn) time, and then we’re iterating through the whole interval vector once and erasing some intervals. Now, the time complexity of v.erase() is O(n) and that of traversing the whole vector once is also O(n). So in total, this will be O(n^2). Thus the total time taken is O(nlogn+n^2) ~ O(n^2).
Space Complexity
O(N), where N is the number of intervals.
Reason: We’re sorting in place, but the sorting algorithm itself takes O(N) space in the worst case.
Approach 2: Optimised Approach using another vector.
Another approach with a better time complexity is to first sort the intervals according to their starting point. Once we have sorted, making the comparisons becomes an easy task. Because if the intervals are sorted, and if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] can’t overlap with interval[i-1] because start[i+1]>start[i]>start[i-1].
The steps are as follows :
Sort the intervals according to their starting time.
Declare and initialize an “ans” vector which will contain all the mutually exclusive intervals.
Traverse the sorted array of intervals from i=0 to i<n and, for each i,
First, insert the interval[0] into ans.
For the subsequent intervals,
If the start time of the interval is greater than the end time of the last pushed interval, then this doesn’t overlap and we can push this to ans.
Otherwise, they overlap, and we have to merge them. For merging, if the end of the previous pushed interval is less than the end of the current interval, update it to the end of the current interval, i.e; take the maximum of both the end times.
4. Return ans.
Implementation
Let’s see the implementation of the above approach.
#include<bits/stdc++.h> usingnamespace std;
vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(),intervals.end()); //sort the intervals based on their //start time int n=intervals.size(); vector<vector<int>> ans; //Declare and initialize the ans vector for(int i=0;i<n;i++){ if(ans.empty()==1){ //if the ans vector is empty, which will be case when //i=0, then just push the current interval into ans ans.push_back(intervals[i]); } else{ //otherwise, if the end time of the last pushed interval is less than //the start time of the current interval, then they don't overlap. So just push it //into ans if(ans.back()[1]<intervals[i][0]){ ans.push_back(intervals[i]); } //else, the intervals are overlapping and they need to be merged. // For merging, just update the end time of the last pushed interval //to max of the end time of that interval and the current interval. else{ ans.back()[1] = max(ans.back()[1],intervals[i][1]); } } } return ans; }
intmain(){ int n; // number of intervals cin>>n; vector<vector<int>>intervals(n); //vector for storing all the intervals for(int i=0;i<n;i++){ int start,end; cin>>start>>end; // start and end time of all the intervals intervals[i].push_back(start); intervals[i].push_back(end); } vector<vector<int>>ans = merge(intervals); // vector for storing all the //mutually exclusive intervals //Printing ans for(auto x:ans){ for(auto y:x){ cout<<y<<" "; } cout<<endl; } return0; }
Input
n=4 , intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]
Complexities
Time Complexity
O(nlogn), where n is the number of intervals.
Reason: Since sorting takes O(nlogn) time, and then we’re iterating through the whole interval vector once, which takes another O(n) time. Thus the total time taken is O(nlogn+n)~O(nlogn).
Space Complexity
O(N), where N is the number of intervals.
Reason: We’re sorting in place, but the sorting algorithm itself takes O(N) space in the worst case. Also we are using another vector of size N for storing answers. So overall space complexity is O(N)+O(N) = O(2N) asymptotically which is equal to O(N).
If you've made it this far, congratulations, Champ. The problem of "Merge intervals " is now resolved. If you haven't already submitted it to Coding Ninjas Studio. Without further ado, have it accepted as early as possible.
Frequently asked questions
How do you combine intervals? Answer: Let’s say we have two intervals [a,b] and [c,d] overlapping with each other as a<c<b<d. Then, after merging, the final interval will be [a,d]. So basically, in merging two intervals, we try to find the both extreme points, i.e; th smallest starting point of the two and the largest ending time of the two.
What is the best time complexity of the solution for merge intervals? Answer: The best solution for the merge intervals problem has a complexity of O(nlogn).
Where can I submit my “Merge intervals” code? Answer: You can submit your code on Coding Ninjas Studio and get it accepted right away.
Are there more Data Structures and Algorithms problems in Coding Ninjas Studio? Answer: Yes, Coding Ninjas Studio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.
Key Takeaways
In this article, we discussed the merge intervals problem which is quite similar to the job scheduling problem which involves scheduling jobs such that any two jobs don’t overlap with each other. So you should try solving it.
To practice more such problems, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.
38+ registered 