Merge Intervals
The problem
Merge all overlapping closed intervals from an unsorted list and return a list sorted by start. Intervals touching at an endpoint should merge.
Example
[[5, 7], [1, 3], [3, 6]] → [[1, 7]]
Need a hint?
Sorting makes every possible overlap adjacent to the current merged interval.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Sort by start. Keep a current merged interval. If the next start is at most its end, extend the end to the maximum of both ends. Otherwise emit the current interval and start a new one. Emit the final interval; empty input yields empty output.
Complexity
O(n log n) time and O(n) result space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.