56. Merge Intervals

Problem

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.

Explanation

Final solution: sort then sweep to merge

The core trick is to sort by the start times. After sorting, overlapping intervals must be adjacent. Keep a current interval initialized to the first one, then iterate forward:

• If the next interval starts before or at current's end, merge by extending current's end to max(current.end, next.end).
• Otherwise, push current into the result and move current to the next interval. Finish by pushing the last current. Sorting dominates the complexity.

Time: O(n log n) due to sorting
Space: O(n) for the output (extra space O(1) beyond output)

Solution