Merge Intervals

Write a function that merges all overlapping intervals. An interval [a, b] overlaps with [c, d] if there is some real number x such that a ≤ x ≤ b and c ≤ x ≤ d.

How to Solve

Sort intervals by start time. Iterate through sorted intervals, merging consecutive intervals if the current interval's start is less than or equal to the previous interval's end. Otherwise, add the previous merged interval to the result and start a new one.

Code

const merge = (intervals: number[][]): number[][] => {
  // Your implementation here
};

Test Cases

Input 1

const intervals1 = [[1, 3], [2, 6], [8, 10], [15, 18]];

Expected Output: [[1, 6], [8, 10], [15, 18]] ([1,3] and [2,6] overlap, merged to [1,6])

Input 2

const intervals2 = [[1, 4], [4, 5]];

Expected Output: [[1, 5]] (adjacent intervals are merged)

Input 3

const intervals3 = [[1, 4], [0, 4]];

Expected Output: [[0, 4]] ([0,4] completely contains [1,4])

Complexity

Time Complexity: O(n log n) - Sorting takes O(n log n), then a single O(n) pass to merge.

Space Complexity: O(n) - In the worst case, no intervals merge, so we store all n intervals in the result array.