Introduction
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.
For example :
INPUT : intervals [ ] = [[1,3],[2,6],[8,10],[15,18]] OUTPUT: [[1,6],[8,10],[15,18]] Intervals [1,3] and [2,6] overlap with each other, therefore, we merge them into [1,6]. Thus, we have the answer as [[1,6],[8,0],[15,18]]. INPUT : intervals[ ] = [[1,4],[4,5]] OUTPUT: [[1,5]] Intervals [1,4] and [4,5] overlap with each other, therefore, merge them into [[1,5]]. Thus we have the answer as [[1,5]]. |
Note: We donβt do anything to the intervals which are not overlapping.
Before directly jumping to the solution, we suggest you try and solve this problem, Merge intervals on Coding Ninjas Studio.
Approach 1: Brute Force
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 :
|
Also see, Euclid GCD Algorithm
Implementation
Letβs see the implementation of the above approach.
| #include<bits/stdc++.h> using namespace std; void compare(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; } int main(){ 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; } return 0; } |
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 :
4. Return ans. |
Implementation
Letβs see the implementation of the above approach.
| #include<bits/stdc++.h> using namespace 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; } int main(){ 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; } return 0; } |
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.
Recommended Problems -
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.
Happy Coding!
