CODING CHALLENGE · N°26

Merge Intervals

Medium SortingArraysInterview Classic

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].

EXAMPLE 1

Input intervals = [[1,3],[2,6],[8,10],[15,18]]

Output [[1,6],[8,10],[15,18]]

[1,3] and [2,6] overlap

EXAMPLE 2

Input intervals = [[1,4],[4,5]]

Output [[1,5]]

touching endpoints merge

EXAMPLE 3

Input intervals = [[1,10],[2,3]]

Output [[1,10]]

nested intervals disappear into the outer one

CONSTRAINTS

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.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement merge_intervals(intervals) → the minimal list of non-overlapping intervals covering the input, sorted by start.

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.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Sort the intervals by start, then sweep left to right holding one “current” merged interval. If the next interval starts at or before the current end, they overlap — extend the current end to max(current end, next end). Otherwise the current interval is finished: push it and start a new current from the next interval.

Complexity

Time O(n log n), dominated by the sort; space O(n) for the output (O(1) extra beyond that).

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 ≤.

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.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA