Example 1 · empty
- Arguments
- intervals
[]
- Expected return
[]
Test data
- Input
{"intervals":[]}- Expected output
[]
Merge overlapping intervals
Merge overlapping intervals
MediumYour task
- Combine overlapping intervals and return their union, sorted by start.
- Each interval is closed: both endpoints count.
- For example, [1,3] and [3,5] touch and must merge into [1,5].
Required API
- MergeIntervals
func MergeIntervals(intervals [][2]int) [][2]int
Behavior
- A gap still separates intervals, even between adjacent integers: [1,2] and [3,4] remain separate.
- Zero-length intervals and duplicate intervals are valid.
- Empty input returns an empty array.
- Leave every input interval and the outer array unchanged.
- Separate calls must not share state.
- Aim for O(n log n) time and O(n) extra space using only the standard library.
- Explain why a nested interval must never shrink the current merged end.
Constraints
- The input is valid: 0–250 intervals in any order.
- Each interval contains exactly two integers between -100,000 and 100,000 inclusive, with start <= end.
- Reversed intervals are outside the input contract.
Notes and example notation
Examples use {"intervals": [[start, end], ...]}.
Examples
The runner calls your functions directly; you do not need to parse JSON.
Example 2 · overlap
- Arguments
- intervals
[ [ 5, 8 ], [ 1, 4 ], [ 3, 6 ] ] - Expected return
[ [ 1, 8 ] ]
Test data
- Input
{"intervals":[[5,8],[1,4],[3,6]]}- Expected output
[[1,8]]
Example 3 · touching
- Arguments
- intervals
[ [ 1, 3 ], [ 3, 5 ], [ 8, 10 ] ] - Expected return
[ [ 1, 5 ], [ 8, 10 ] ]
Test data
- Input
{"intervals":[[1,3],[3,5],[8,10]]}- Expected output
[[1,5],[8,10]]
Example 4 · nested
- Arguments
- intervals
[ [ 1, 10 ], [ 2, 3 ], [ 4, 8 ] ] - Expected return
[ [ 1, 10 ] ]
Test data
- Input
{"intervals":[[1,10],[2,3],[4,8]]}- Expected output
[[1,10]]
Solution guide
Reveal solution guide — spoilers
Approach
- Copy the intervals, including independent pair storage where needed, and sort the copy by start position. Do not sort or mutate the original outer array or its intervals.
- Maintain a current merged interval. If the next start is less than or equal to its end, extend that end to the maximum of the two ends.
- If the next start is greater than the current end, emit the current interval and start a new one. Emit the final interval after the scan; empty input returns an empty result.
Why it works
Sorting ensures every unseen interval starts no earlier than the next interval under consideration. Once a gap appears, no later interval can connect back to the completed current interval. Taking the maximum end preserves the entire union when an interval is nested. Equality merges because endpoints belong to closed intervals.
Complexity
O(n log n) time for sorting and O(n) extra space for the independent copy/output. The merge scan is O(n).
Edge cases to check
- [1, 3] and [3, 5] merge, but [1, 2] and [3, 4] remain separate; do not add one to the end for integer adjacency.
- Nested, duplicate and zero-length intervals must not shrink a previously extended end.
- Unsorted input is valid; reversed endpoints are outside the contract and need no repair.
Restoring local drafts…
Checking execution availability…
Public examples
NO CODE EXECUTEDExplore the examples.
View inputs and expected outputs. Examples do not run your code.