Merge Intervals

Shreya Deep
Last Updated: May 13, 2022

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

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 :

  • 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: 
    1.  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.
    2. 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
  • Return the intervals vector.

 

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 :

  1. Sort the intervals according to their starting time.
  2. Declare and initialize an “ans” vector which will contain all the mutually exclusive intervals.
  3. 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,
      1.  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. 
      2. 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>
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 CodeStudio. Without further ado, have it accepted as early as possible.

Frequently asked questions

  1. 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. 
     
  2. 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).
     
  3. Where can I submit my “Merge intervals” code?
    Answer: You can submit your code on CodeStudio and get it accepted right away.
     
  4. Are there more Data Structures and Algorithms problems in CodeStudio?
    Answer: Yes, CodeStudio 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, Codestudio 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!
 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think