Data Structures & Algorithms (Merge Intervals): Merge Intervals

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Example 3:

Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.

Solve Here: Leetcode 56

General Observations

Q. Are the intervals sorted by the start time?
A. No, the intervals are not guaranteed to be sorted by the start time.

Intuition

If intervals are in arranged in random order, each interval can overlap with any other interval. However, if the intervals are sorted by start time, we can iterate through each interval and compare it with the last merged interval in the result list to check for overlap.

How to Check if Two Intervals are Overlapping?

For two intervals A = [start1, end1] and B = [start2, end2] where start1 <= start2, overlap exists if start2 <= end1.

How to Merge Two Intervals?

For two intervals A = [start1, end1] and B = [start2, end2] where start1 <= start2 (sorted) and start2 <= end1 (overlapping), the merged interval is [start1, max(end1, end2)].

Algorithm

public int[][] merge(int[][] intervals) {

    // Sort intervals in ascending order of their start time.
    Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0])); // a[0] - b[0] can overflow when values are large

    List<int[]> result = new ArrayList<>();

    for(int[] interval: intervals) {
        if(result.isEmpty()) {
            result.add(interval);
        } else {
            int[] lastMerged = result.get(result.size() - 1);
            // Check if current intervals starts with last merged interval ends (overlapping)
            if (interval[0] <= lastMerged[1]) {
                lastMerged[1] = Math.max(lastMerged[1], interval[1]);
            } else {
                result.add(interval);
            }
        }
    }

    return result.toArray(new int[result.size()][]);
}

Visualization

Time Complexity

We are only iterating over the intervals once. Hence, overall time complexity = O(n).

Space Complexity

In worst-case scenario (no overlapping intervals), the result array would store all n intervals. Hence, overall space complexity = O(n).