Challenge
Return the union of the supplied closed intervals as sorted, disjoint [start, end] pairs. Intervals that touch at an endpoint must merge: [1, 3] and [3, 5] become [1, 5]. Duplicate intervals do not create duplicate output.
Input and output contract
0 ≤ n ≤ 2,000; integer endpoints between -1,000,000 and 1,000,000; start ≤ end. Input order is arbitrary. Empty input returns [].
All tests follow this contract. You do not need to validate malformed input. Return the requested result from merge_intervals; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(n log n) time; O(n) space including sorted copy and output
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[[[5, 7], [1, 3], [3, 5], [9, 9]]]
Expected return
[[1, 7], [9, 9]]
Arguments
[[]]
Expected return
[]
Arguments
[[[1, 10], [2, 3]]]
Expected return
[[1, 10]]
Hint
Sort by start. Only the last interval in the merged output can overlap the next one.
The worked solution unlocks after completion, or with Premium access.