intervals · Problem 2 of 2
Merge Intervals
Given a list of [start, end] intervals, merge every pair that overlaps and
return the result sorted by start.
mergeIntervals([[1, 3], [2, 6], [8, 10]]) -> [[1, 6], [8, 10]]
Touching counts as overlapping: [1, 4] and [4, 5] merge into [1, 5].
Almost every interval problem starts the same way, and that first step is most of the difficulty — in an unsorted list, any interval can overlap any other, so there is no single pass that works.
Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| mergeIntervals([[1,3],[2,6],[8,10]]) | two overlap, one stands alone | [[1,6],[8,10]] | — |
| mergeIntervals([[1,4],[4,5]]) | touching intervals merge | [[1,5]] | — |
| mergeIntervals([[8,10],[1,3],[2,6]]) | given out of order | [[1,6],[8,10]] | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n log n)
- target space
- O(n)
The sort dominates — the merge itself is one pass. That is the shape of most interval problems: sorting is what turns an all-pairs question into a neighbours-only one.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left