3.10 Merge Intervals

3.10.1 Problem Metadata

3.10.2 Description

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return the result in ascending order of start time.

3.10.3 Examples

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

3.10.4 Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4

3.10.5 Solution - Sort then Merge

3.10.5.1 Walkthrough

Sort the intervals by starting point. Iterate through them, merging with the last interval in the output when an overlap occurs (current.start <= last.end), otherwise append the new interval.

3.10.5.2 Analysis

  • Time Complexity: O(n log n)
  • Space Complexity: O(n) for the output lc-list

3.10.5.3 Implementation Steps

  1. Sort intervals ascending by start.
  2. Initialize an empty lc-list merged.
  3. For each interval:
    1. If merged is empty or current.start > merged.last.end, append interval.
    2. Else set merged.last.end = max(merged.last.end, current.end).
  4. Return merged as an array.

3.10.5.4 Code - Java

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) {
        return new int[0][0];
    }

    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    List<int[]> merged = new ArrayList<>();
    merged.add(intervals[0].clone());

    for (int i = 1; i < intervals.length; i++) {
        int[] current = intervals[i];
        int[] last = merged.get(merged.size() - 1);

        if (current[0] <= last[1]) {
            last[1] = Math.max(last[1], current[1]);
        } else {
            merged.add(current.clone());
        }
    }

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