Merge overlapping intervals
Merge closed integer intervals whenever they overlap or touch at an endpoint. Return disjoint intervals ordered by their starts; adjacent intervals such as [1,2] and [3,4] do not overlap. All input is valid JSON satisfying the constraints; do not mutate the meaning of values through type coercion. Interviewers use this problem to assess sort intervals by start and extend the current merged interval.
Input
A JSON array of [start,end] pairs.
Output
Print one compact JSON value: an array of merged [start,end] pairs.
Constraints
0 <= interval count <= 10000; -1000000 <= start <= end <= 1000000.
Example
Input
[[1,3],[2,6],[8,10],[10,12]]
Output
[[1,6],[8,12]]
Example 2 input
[[-3,0],[0,2],[3,4]]
Output
[[-3,2],[3,4]]
Boundary case: Equal endpoints overlap because intervals are closed
Public test cases (2)
Input
[[1,3],[2,6],[8,10],[10,12]]
Expected output
[[1,6],[8,12]]
Input
[[5,7],[1,2]]
Expected output
[[1,2],[5,7]]
Hints (2)
- Only the most recent merged interval can overlap the next interval
- Equal endpoints overlap because intervals are closed
Target complexity: time O(n log n) · space O(n)