Pattern 1: Sort and merge

Merging overlapping intervals is the "hello, world" of the section. And it shows, in its purest form, the method that works for almost everything here: sort by start, then scan once.

🎯

Try it first: Merge Intervals

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Given a list of intervals [start, end], merge all the overlapping ones and return the resulting list (sorted by start).

Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]] ([1,3] and [2,6] overlap → [1,6]).

Carregando editor…

Tried it? Without sorting, you end up comparing each interval against all the others (O(n²)) and still get lost with chained overlaps. The theory below shows why sorting first makes everything simple.

The theory: sorting transforms the problem

Why does sorting by start help so much? Because, after that, any interval that overlaps a previous one can only overlap the last one you processed (all the earlier ones already ended further to the left). This reduces "compare with all" to "compare with the last one in the result":

sort by start
result = []
for each [start, end]:
    if result not empty AND start <= end of last in result:
        # overlaps → extend the end of the last
        last.end = max(last.end, end)
    else:
        # no overlap → start a new block
        result.append([start, end])

Note the max when extending: the current interval may be contained in the last one (e.g., [1,6] swallowing [2,4]), so the end must not shrink. Watch the scan — the top row is the input (current one highlighted), the bottom row is the result being built and extended:

Execução real, gravada passo a passo

Carregando Python no navegador (primeira vez demora alguns segundos)…

Why is it O(n log n) time and O(n) space?

The sort costs O(n log n) and dominates. The scan is a single O(n) pass, comparing each interval only with the last one in the result. Space is O(n) for the output list (or O(log n)–O(n) for the sort itself). The brute force of comparing all pairs would be O(n²) — sorting is what knocks that down.

The reflex that defines the section

This is the mother template of intervals: sort by one endpoint + one scan comparing against the accumulated state. Memorize the shape of the code — the next lessons are variations of it (insert changes "when to start merging," the greedy one changes the sorting criterion, the event sweep changes what you accumulate).

🧠 Review quiz

0/4

1. Why does sorting by start simplify merging intervals?

2. When merging an overlapping interval, why use max(last.end, current.end) instead of just current.end?

3. What is the complexity of merge and what dominates it?

4. What is the 'mother template' of interval problems, of which merge is the example?

Summary

Merge: sort by start; scan, merging when start <= end of the last (with max on the end).
O(n log n) (sort dominates), O(n) space; far better than the naive O(n²).
It's the mother template of the section: sort + scan with accumulated state.

Next lesson: insert an interval into a set that's already sorted.

All lessons in this section