Intervals — Merge Overlapping Intervals

intervals is a list of [start, end] pairs, in no particular order.
Merge every group of overlapping intervals and return the result **sorted by
start**.

Two intervals overlap when one starts before or exactly when the other ends:
[1, 4] and [4, 5] touch, and merge into [1, 5].

Sort by start, then walk once: each interval either extends the last merged one
or starts a new one. O(n log n) for the sort, O(n) for the walk.

Examples

solve([[1, 3], [2, 6], [8, 10], [15, 18]])  → [[1, 6], [8, 10], [15, 18]]
solve([[1, 4], [4, 5]])                     → [[1, 5]]
solve([[1, 4], [0, 2], [3, 5]])             → [[0, 5]]

Constraints

• 1 <= intervals.length <= 10000
• start <= end for every interval.
• Do not modify the input arrays.