Write merge(intervals: list[list[int]]) -> list[list[int]].
Each interval is [start, end] with start <= end, and the input is in no particular order. Merge every group of overlapping intervals into one and return the result sorted by start. Intervals that touch, like [1, 4] and [4, 7], count as overlapping and merge into [1, 7].
Example: [[8, 9], [1, 4], [2, 5], [11, 14]] gives [[1, 5], [8, 9], [11, 14]].
[[1, 4], [4, 7]] gives [[1, 7]], and [] gives [].
Constraints: up to 10^5 intervals, 0 <= start <= end <= 10^9.
Repeatedly comparing every pair is O(n²) and fails the large test; aim for O(n log n). Remember that an interval can be swallowed completely by an earlier, longer one.
Follow-up (not tested): how would you return the total length covered by the union instead, and what changes if coordinates can be negative?
Show hint
once the intervals are in a good order, each one either joins the last merged block or starts a new one.