Coding · Intervals
Merge Intervals
- Reported in several places
- Medium
- L3
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
You are given a list of closed intervals [start, end] in no particular order. Combine every group of intervals that overlap or touch, and return the combined intervals sorted by start. For example, [[8,10],[1,3],[2,6],[15,18]] becomes [[1,6],[8,10],[15,18]]. There can be up to 10,000 intervals, and the numbers are integers.
Restated in our own words, not a quote from Google or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
First I would confirm what overlapping means. Do [1,4] and [4,5] merge because they share the point 4? I will assume yes, since the intervals are closed. Then: is the input sorted? Can it be empty? Can an interval be a single point like [3,3]? Can numbers be negative? Should I return a new list or edit the input? And how many intervals are there, to know whether an O(n²) approach could pass?
Assumptions I would state: closed intervals, start never greater than end, unsorted input, up to 10,000 intervals, an empty input returns an empty list, and the input is left unchanged.
Brute force
Say the obvious answer and why it is too slow.
The obvious approach compares pairs. Take an interval, scan the rest for one that overlaps it, replace the two by their union, and start again. Stop when a full scan finds nothing to merge. It needs no sorting and is easy to get right.
The cost is the problem. One scan over all pairs is O(n²), and a merge can unlock new merges (a long interval can bridge two others that did not touch before), so you may need up to n scans. Worst case O(n³). At 10,000 intervals one scan is already 50 million pair checks and n³ is around a trillion. The waste is that every interval gets compared with far away intervals that can never touch it.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n³)
- Time
- O(n log n)
- Space
- O(n) for the copy and the result
The pattern is sort, then sweep. Sort the intervals by start. After that an interval can only reach the ones next to it in sorted order, so one left-to-right pass is enough.
Keep a list of merged blocks and look only at its last block, the one still growing. For the next interval in sorted order ask a single question: does its start fall at or before the end of that last block? If yes, they overlap or touch, so set the block's end to the larger of the two ends. The maximum matters, because the new interval can sit entirely inside the block. If no, there is a gap, so the new interval opens a fresh block.
Why is it correct? Because the starts are sorted, every interval not yet seen starts at or after the current one. If the current interval starts beyond the last block's end, then every later interval does too, so that block is finished for good and nothing can ever extend it. Only the newest block can still grow, so checking only the last block is not a shortcut. It is the only check there is. After each step the merged list is exactly the answer for the intervals seen so far.
Out loud: "Sort by start, then walk once. Either the next interval starts inside my current block, so I extend the end with a max, or it starts after it, so I close the block and open a new one. The sort costs O(n log n) and the walk costs O(n)."
Walk it through
A dry run on the example, step by step.
| Step | Next interval | Last block | Decision | Blocks so far |
|---|---|---|---|---|
| 1 | [1,3] | none | no block, open one | [1,3] |
| 2 | [2,6] | [1,3] | 2 <= 3, end becomes 6 | [1,6] |
| 3 | [8,10] | [1,6] | 8 > 6, open new | [1,6] [8,10] |
| 4 | [15,18] | [8,10] | 15 > 10, open new | [1,6] [8,10] [15,18] |
Take [[8,10],[1,3],[2,6],[15,18]]. Sorting by start gives [1,3], [2,6], [8,10], [15,18]. The table follows the sweep.
The first interval has no block before it, so it opens [1,3]. Next is [2,6]: its start 2 is at most the block end 3, so they overlap and the end becomes max(3,6) = 6. Next is [8,10]: 8 is greater than 6, so there is a gap and a new block opens. Last is [15,18]: 15 is greater than 10, so another new block opens. Each interval is looked at once, and the only thing ever compared is its start against the end of the last block. The final column of the table is the answer.
The code
Runnable JavaScript, checked against test cases.
function mergeIntervals(intervals) {
const sorted = intervals
.map((pair) => [pair[0], pair[1]])
.sort((a, b) => a[0] - b[0]);
const merged = [];
for (const [start, end] of sorted) {
const lastBlock = merged[merged.length - 1];
if (lastBlock && start <= lastBlock[1]) {
lastBlock[1] = Math.max(lastBlock[1], end);
} else {
merged.push([start, end]);
}
}
return merged;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty input: the loop never runs and the result is an empty list.
- One interval: it opens a block and nothing else happens.
- Touching intervals: [1,4] and [4,5] merge because the test is start <= end. If the problem used open intervals, the test would become a strict less-than.
- Nested intervals: [1,10] with [2,3] keeps end 10 because of the max.
- Identical intervals: the copy starts inside the block and changes nothing.
- Single points and negatives: [3,3] and negative numbers work, since only comparisons are used.
- Caller's data: the code copies each pair before sorting, so the input is not changed.
Follow-ups to expect
Where the interviewer pushes next.
- How would you insert one new interval into an already merged, sorted list in O(n) time?
- What changes if the input is already sorted by start, and what is the running time then?
- How would you list the gaps between the merged intervals, or count the most intervals that overlap at once?
- How would you answer 'is this point covered?' when intervals arrive one at a time?
- How would you merge intervals from a file too large to hold in memory?
Where candidates slip
The mistakes this problem punishes.
The classic mistake is skipping the sort, or calling sort() with no comparator. JavaScript then compares numbers as strings, so [10,12] lands before [2,3] and the sweep silently breaks.
- Writing
last[1] = endinstead of the max, which shrinks a block when the new interval is nested. - Using a strict less-than and failing to merge touching intervals.
- Comparing the new interval with the previous input interval instead of the last merged block.
- Pushing the original pair and then editing it, which changes the caller's input.
- Forgetting the empty input, so reading the last block of an empty list throws.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.