Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path →
Merge Intervals
Calendar apps, memory allocators, and half of all interview loops run on this: sort intervals by start, then sweep once, growing or closing the current merged block. The classic that punishes off-by-one thinking at the boundaries.
The problem
Given intervals, a list of [start, end] pairs (start ≤ end, any order), merge all overlapping intervals and return the result sorted by start. Two intervals overlap if one starts before or exactly when the other ends — touching intervals like [1,4] and [4,5] merge into [1,5].
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? open the hints under the problem, or Reveal solution is one click away.
Implement merge_intervals(intervals) → the minimal list of non-overlapping intervals covering the input, sorted by start.
Examples and constraints 4 examples
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]intervals = [[1,4],[4,5]][[1,5]]intervals = [[1,10],[2,3]][[1,10]]intervals = [[8,10],[1,3],[2,6]][[1,6],[8,10]]- Input may be unsorted — sort by start first.
- Touching counts as overlapping: next.start ≤ current.end merges.
- Merging takes max(end) — nested intervals must not shrink the block.
Hints 4 ideas
- Sort by start. After that, only the CURRENT merged block can ever absorb the next interval.
- If next.start ≤ current.end, extend: current.end = max(current.end, next.end).
- Otherwise close the block, append it, and start a new one.
- The nested case [[1,10],[2,3]] is why the max() matters.
Approach, complexity & discussion — open after you solve
Start from brute force
Compare every pair. Build an overlap graph with an edge between any two intervals that intersect, find its connected components, and report each component as [min start, max end]. It is correct because overlap chains are exactly what merges, and the union of a connected run of intervals on a line is one interval. But the pair checks alone are O(n²) time, and storing the edges is up to O(n²) space: at 10⁴ intervals that is about 50 million comparisons. The repeat-until-stable version, which merges any overlapping pair and rescans, is worse, up to O(n³) when each pass finds one merge.
The approach
Sort by start, and the problem collapses to one comparison per interval. The reference merge_intervals returns [] for empty input, then sorts a copy with sorted(intervals, key=lambda iv: iv[0]) and seeds out with list(ivs[0]), a copy so the caller’s data is never mutated. For each later (s, e): if s <= out[-1][1] the interval overlaps or touches the current block, so the block’s end becomes max(out[-1][1], e); otherwise the block is finished and [s, e] starts a new one.
The invariant: out is always the merged answer for the intervals read so far, sorted and non-overlapping, and only its last block can still grow. Every later interval starts at or after that block’s start, while every earlier block ends before it begins, so nothing can reach back past the current block. The <= makes touching intervals merge, and the max keeps a nested interval from shrinking the block. The TypeScript mergeIntervals sorts a copy with (a, b) => a[0] - b[0].
max, otherwise it closes the block and opens a new one.Walk through an example
On the first example the input is already sorted, so the sweep extends one block and then opens two more.
| step | interval | test against current end | action | out |
|---|---|---|---|---|
| 1 | [1, 3] | first after sorting | seed the first block | [[1, 3]] |
| 2 | [2, 6] | 2 ≤ 3 | extend: end = max(3, 6) = 6 | [[1, 6]] |
| 3 | [8, 10] | 8 > 6 | close the block, append | [[1, 6], [8, 10]] |
| 4 | [15, 18] | 15 > 10 | close the block, append | [[1, 6], [8, 10], [15, 18]] |
Complexity
Time O(n log n), all of it the sort; the sweep is O(n) with constant work per interval. Space O(n) for the sorted copy and the output; sorting in place would leave only the sort’s own auxiliary space beyond the output. The pairwise overlap graph is O(n²) time and up to O(n²) space for its edges.
Edge cases to test
[[1, 4], [4, 5]]→[[1, 5]]. Touching intervals merge; a strict<test returns two intervals.[[1, 10], [2, 3]]→[[1, 10]]. Setting the end to the new interval’s end instead of the max shrinks the block to[1, 3].[[1, 5], [2, 3], [4, 6]]→[[1, 6]]. Comparing with the previous interval’s end (3) instead of the block’s end (5) wrongly splits off[4, 6].[[8, 10], [1, 3], [2, 6]]→[[1, 6], [8, 10]]. Unsorted input; sweeping without sorting misses that[1, 3]and[2, 6]overlap.[]→[]. The reference returns early, before readingivs[0], which would raise on an empty list.[[2, 2], [2, 3]]→[[2, 3]]. A zero-length interval is still an interval and touches its neighbor.
Common mistakes
- Forgetting to sort by start first — the single-pass merge only works on sorted intervals.
- Extending to the next interval’s end instead of
max(current, next)— a nested interval then wrongly shrinks the merge. - Getting the touch case wrong —
[1,2]and[2,3]usually merge, so test overlap with≤.
Follow-ups an interviewer asks next
- Insert one new interval into a list that is already merged and sorted.
- No sort is needed. Copy the intervals that end before the new one starts, absorb every interval that overlaps it by taking the minimum start and maximum end, then copy the rest. That is one O(n) pass. Binary search can locate the overlapping run in O(log n), but rebuilding a Python list or JavaScript array is still O(n).
- Intervals keep arriving. Maintain the merged set as you go.
- Keep the merged blocks in a balanced search tree or sorted map keyed by start. On each insert, look up the neighbor just before the new start and the blocks after it, merge every one that overlaps, and remove the absorbed blocks. Each insert is O(log n) plus the merges, and since a block disappears at most once, the merges cost O(log n) amortized.
- The intervals are half-open, like calendar slots.
- Then
[1, 4)and[4, 5)do not overlap, because the first ends exactly when the second begins. Change the test tos < out[-1][1]and keep everything else. The boundary convention is the first thing to confirm in an interview, since it changes the answer on every touching pair. - Return the intersection of two lists that are each sorted and already merged.
- Walk both with two pointers. The overlap of the current pair is
[max(starts), min(ends)], kept if its start is at most its end; then advance whichever interval ends first, since it cannot overlap anything later in the other list. For[[0,2],[5,10]]and[[1,5],[8,12]]that gives[[1,2],[5,5],[8,10]], in O(m + n) time with no sort. - How many meeting rooms do these meetings need?
- That asks for the maximum overlap depth, not the union, so merging loses the answer. Sort the starts and the ends separately and sweep both, adding one at each start and subtracting one at each end, and track the peak; or keep a min-heap of end times. Both are O(n log n).
Where this shows up
Interval merging is the engine behind calendar and booking conflict detection, coalescing IP/CIDR or genomic ranges, and the broader sweep-line family of algorithms. “Sort, then sweep while maintaining a running state” is one of the most reused patterns in scheduling and computational geometry.
Finding free time. A scheduler that wants a slot when everyone is free merges every attendee’s busy intervals into one list and reads the gaps between consecutive blocks. With the first example as the busy times inside a window from 0 to 20, the merged blocks [1,6], [8,10], [15,18] leave the free slots [0,1], [6,8], [10,15], [18,20]. The merge is what makes this correct: comparing each interval with only the previous one fails on nesting, so busy times [1,10], [2,3], [5,6] would report 3 to 5 as free although [1,10] covers it.
Total coverage. The length of a union of intervals is the sum of the merged lengths, never the sum of the input lengths. The example covers 5 + 2 + 3 = 10 units, while its inputs add up to 2 + 4 + 2 + 3 = 11, because 2 to 3 is counted twice. Billing for time a machine was in use, or measuring how much of a genome some set of reads covers, is this computation; genomics toolkits such as bedtools ship it as a merge command.
Integer ranges. Ranges of IP addresses, port numbers or row IDs are sets of whole numbers, so [0, 255] and [256, 511] cover a continuous run even though 255 ≠ 256. Merging them takes the test s <= end + 1, the third boundary convention after closed and half-open, and the one that turns adjacent address blocks into a single, shorter rule.
Check yourself
Predict merge_intervals([[5, 7], [1, 2], [6, 9], [2, 4], [10, 11]]).
[[1, 4], [5, 9], [10, 11]]. Sorted it is [1,2], [2,4], [5,7], [6,9], [10,11]: [2,4] touches [1,2] and merges because the test is <=, 5 > 4 opens a block that [6,9] extends, and 10 > 9 opens the last. Note that 4 and 5 do not merge: they are adjacent integers, not touching endpoints.
A colleague sorts by end and keeps the same sweep. What does it return for [[2, 3], [4, 5], [1, 10]]?
[[2, 3], [4, 10]] instead of [[1, 10]]. Sorted by end, [1, 10] comes last and overlaps both earlier blocks, but the sweep only compares with the last one and never reopens [2, 3]. Sorting by start is what guarantees no interval reaches back past the current block.
Switch the test to the half-open s < out[-1][1]. What happens to [[1, 4], [4, 5], [5, 7]]?
It stays as three intervals, [[1, 4], [4, 5], [5, 7]], where the reference returns [[1, 7]]. Every pair only touches, so the boundary convention alone decides the answer: one comparison operator turns one block into three.
Every start and end is an integer in [0, 10⁴]. Can you beat O(n log n)?
Yes, O(n + R) with R = 10⁴ + 1: keep an array best[start] = max end over intervals with that start, then sweep the starts in increasing order with the same extend-or-close rule. That is a counting sort in place of a comparison sort. Marking covered integer points instead would be wrong: it fuses [1, 2] and [3, 4], which do not touch.
Reference solution
Reference solution — Python
def merge_intervals(intervals):
if not intervals:
return []
ivs = sorted(intervals, key=lambda iv: iv[0])
out = [list(ivs[0])]
for s, e in ivs[1:]:
if s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return out
print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]])) # -> [[1, 6], [8, 10], [15, 18]]Reference solution — TypeScript
function mergeIntervals(intervals: number[][]): number[][] {
if (intervals.length === 0) return [];
const ivs = [...intervals].sort((a, b) => a[0] - b[0]);
const out: number[][] = [[...ivs[0]]];
for (let i = 1; i < ivs.length; i++) {
const [s, e] = ivs[i];
const cur = out[out.length - 1];
if (s <= cur[1]) cur[1] = Math.max(cur[1], e);
else out.push([s, e]);
}
return out;
}
console.log(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]])); // -> [[1,6],[8,10],[15,18]]Questions about Merge Intervals
Why do you sort by start time to merge intervals?
Sorting by start guarantees that once you move past a merged block, no later interval can reach back and overlap it. Every later interval starts at or after the current block’s start, and every finished block ends before the current block begins, so the only block a new interval can touch is the current one. That turns an all-pairs problem into one comparison per interval. Sorting by end time does not work with the same forward sweep, because a later interval can start early enough to overlap blocks that were already closed.
What is the time complexity of merge intervals?
O(n log n), and the sort is the whole cost. After sorting, the sweep looks at each interval once and does constant work, so it is O(n). Space is O(n) for the sorted copy and the output list; sorting in place reduces the extra space to whatever the sort itself needs. The only faster case is input that is already sorted by start, where the sweep alone is linear. Comparing every pair instead, or building an overlap graph and finding its connected components, costs O(n²).
Should intervals that only touch, like [1, 4] and [4, 5], be merged?
It depends on whether the intervals are closed or half-open, and the problem has to say. This one treats them as closed and says touching intervals merge, so the overlap test is start less than or equal to the current end, and [1, 4] plus [4, 5] becomes [1, 5]. Calendars usually use half-open intervals, where a meeting from 1 to 4 ends exactly when one from 4 to 5 begins and the two do not conflict. There the test is strictly less than, and the intervals stay separate.
Why use max when extending the merged end?
Because the next interval can sit entirely inside the current block. With [1, 10] followed by [2, 3], setting the end to the new interval’s end would shrink the block to [1, 3] and lose the coverage from 3 to 10. Taking the maximum of the current end and the new end keeps the block as wide as everything it has absorbed. A related bug compares against the previous interval instead of the block: in [1, 5], [2, 3], [4, 6], the block end of 5 is what shows that [4, 6] still overlaps.
Explore the topic
See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.
More Challenges
- Two SumThe classic warm-up: find the two numbers that add up to a target. Brute force is O(n²) — a hash map gets you to one pass, O(n). Solve it in Python or TypeScript, right in your browser, with hidden tests and a reveal-solution button.Read →
- Valid ParenthesesThe canonical stack problem: decide whether every bracket is closed by the right type, in the right order. A stack turns nested matching into a single pass. Solve it in Python or TypeScript with hidden tests.Read →
- Fizz BuzzThe famous screening question. Print 1…n, but multiples of 3 become "Fizz", of 5 become "Buzz", and of both become "FizzBuzz". Easy — the catch is testing divisibility in the right order. Solve it in Python or TypeScript.Read →
- Number of IslandsThe canonical connected-components question. Flood-fill each unvisited patch of land with BFS or DFS, count how many floods you started — grid traversal, visited bookkeeping, and the classic diagonal trap. Solve it in Python or TypeScript.Read →
- Top-K Frequent ElementsCount, then rank — the two-step pattern behind trending topics and hot-key detection. A hash map counts; a (-count, value) sort ranks with a clean tie-break; buckets get you to O(n) if you want the flex. Solve it in Python or TypeScript.Read →
- 3SumThe rite of passage: every unique zero-sum triplet, no duplicates, no O(n³). Sort once, fix one element, squeeze the rest with two pointers, and skip duplicates at all three levels. Solve it in Python or TypeScript.Read →