Merge Intervals

Problem Statement:

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

Example 1

Input: intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we merged them into 
one [1,5].

Example 2

Input: intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]]
Explanation: Since the intervals [6,7] and [5,9] overlap, we merged them into one [5,9].

Example 3

Input: intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]]
Explanation: Since all the given intervals overlap, we merged them into one.

Solution

Let’s take an example of two intervals (a and b) such that a.start <= b.start. There are four possible scenarios:

Our goal is to merge the intervals whenever they overlap. For the above-mentioned three overlapping scenarios (2, 3, and 4), this is how we will merge them:

The diagram above clearly shows a merging approach. Our algorithm will look like this:

1. Sort the intervals on the start time to ensure a.start <= b.start.
2. If a overlaps b (i.e. b.start <= a.end), we need to merge them into a new interval c such that:

c.start = a.start
c.end = max(a.end, b.end)

3. We will keep repeating the above two steps to merge c with the next interval if it overlaps with c.

Java Code

import java.io.*;
import java.util.*;

class Innoskrit {

    public static int[][] merge(int[][] intervals) {
    
        if (intervals.length < 2)
            return intervals;
        
        // sort the intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> mergedIntervals = new ArrayList<>();
        
        int[] prevInterval = intervals[0];
        
        int i = 1;
        while (i < intervals.length) {
            int[] interval = intervals[i];
            if (interval[0] <= prevInterval[1]) { // overlapping intervals, adjust the 'end'
                prevInterval[1] = Math.max(interval[1], prevInterval[1]);
            } else { // non-overlapping interval, add the previous interval and reset
                mergedIntervals.add(prevInterval);
                prevInterval = interval;
            }
            i += 1;
        }
        
        // add the last interval
        mergedIntervals.add(prevInterval);
        
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }

    public static void main(String[] args) {
        int[][] intervals = new int[][] {{1, 4}, {2, 5}, {7, 9}};
        for (int[] interval : Innoskrit.merge(intervals))
            System.out.print("[" + interval[0] + "," + interval[1] + "] ");
        System.out.println();
        
        intervals = new int[][] {{6, 7}, {2, 4}, {5, 9}};
        for (int[] interval : Innoskrit.merge(intervals))
            System.out.print("[" + interval[0] + "," + interval[1] + "] ");
        System.out.println();
        
        intervals = new int[][] {{1, 4}, {2, 6}, {3, 5}};
        for (int[] interval : Innoskrit.merge(intervals))
            System.out.print("[" + interval[0] + "," + interval[1] + "] ");
        System.out.println();
    }
}

C++ Code

#include<bits/stdc++.h>
using namespace std;

class Innoskrit {
public:
    static vector<vector<int>> merge(vector<vector<int>> &intervals) {
        
        if (intervals.size() < 2) {
            return intervals;
        }

        // sort the intervals by start time
        sort(intervals.begin(), intervals.end(),
             [](const vector<int> &x, const vector<int> &y) { return x[0] < y[0]; });

        vector<vector<int>> mergedIntervals;

        vector<int> prevInterval = intervals[0];
        int i = 1;
        while (i < intervals.size()) {
            vector<int> interval = intervals[i];
            if (interval[0] <= prevInterval[1]) {  // overlapping intervals, adjust the 'end'
                prevInterval[1] = max(interval[1], prevInterval[1]);
            } else {  // non-overlapping interval, add the previous interval and reset
                mergedIntervals.push_back(prevInterval);
                prevInterval = interval;
            }
            i += 1;
        }
        
        // add the last interval
        mergedIntervals.push_back(prevInterval);
        
        return mergedIntervals;
    }
};

int main(int argc, char *argv[]) {
    vector<vector<int>> intervals = {{1, 3}, {2, 5}, {7, 9}};
    for (auto interval : Innoskrit::merge(intervals)) {
        cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    cout << endl;
    
    intervals = {{6, 7}, {2, 4}, {5, 9}};
    for (auto interval : Innoskrit::merge(intervals)) {
        cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    cout << endl;
    
    intervals = {{1, 4}, {2, 6}, {3, 5}};
    for (auto interval : Innoskrit::merge(intervals)) {
        cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    cout << endl;
}

Python Code

class Innoskrit:    

    def merge(intervals):
        
        if len(intervals) < 2:
            return intervals
        
        # sort the intervals on the start time
        intervals.sort(key = lambda x : x[0])
        
        mergedIntervals = []
        prev_interval = intervals[0]
        for i in range(1, len(intervals)):
            interval = intervals[i]
            if interval[0] <= prev_interval[1]:  # overlapping intervals, adjust the 'end'
                prev_interval[1] = max(interval[1], prev_interval[1])
            else:  # non-overlapping interval, add the previous internval and reset
                mergedIntervals.append(prev_interval)
                prev_interval = interval
        
        # add the last interval
        mergedIntervals.append(prev_interval)
        
        return mergedIntervals


if __name__ == '__main__':
  
    intervals = [[1, 4], [2, 5], [7, 9]]
    for i in Innoskrit.merge(intervals):
        print(i, end = " ")
    print()
    
    for i in Innoskrit.merge([[6, 7], [2, 4], [5, 9]]):
        print(i, end = " ")
    print()
    
    for i in Innoskrit.merge([[1, 4], [2, 6], [3, 5]]):
        print(i, end = " ")
    print()

Output

[1,5] [7,9] 
[2,4] [5,9] 
[1,6]

Time Complexity

The time complexity of the above algorithm is O(N * logN), where ‘N’ is the total number of intervals. We are iterating the intervals only once which will take O(N), in the beginning though, since we need to sort the intervals, our algorithm will take O(N * logN).

Space Complexity

The space complexity of the above algorithm will be O(N) as we need to return a list containing all the merged intervals. We will also need O(N) space for sorting. In the case of Java, depending on its version, Arrays.sort() either uses Merge sort or Timsort, and both these algorithms need O(N) space. Overall, our algorithm has a space complexity of O(N).