Merge Intervals

Anyone who has stared at a shared calendar knows the feeling: a dozen overlapping blocks, and the real question is not what each one says but which stretches of the day are actually busy. That is the whole Merge Intervals pattern. You have a pile of ranges, some of them overlap, and you want the smallest set of clean, non-overlapping ranges that covers the same ground.

The one move that makes it easy is sorting. Ranges scattered in any order are hard to reason about, because an overlap can be with anything. Sort them by start time and overlaps can only ever happen between neighbors, which turns a tangled comparison into a single walk down the list.

Why sorting is the whole trick

Once the intervals are sorted by start, sweep through them holding the last merged interval. Each new one either overlaps it, in which case you stretch the merged interval's end, or it starts past the end, in which case the previous block is finished and this one opens a new block.

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:               # overlaps the current block
            last[1] = max(last[1], end)    # extend it, do not just take end
        else:
            merged.append([start, end])    # a gap, start a fresh block
    return merged

On [[1, 3], [2, 6], [8, 10], [9, 12]] the sort changes nothing, then [2,6] overlaps [1,3] and merges to [1,6], [8,10] starts past 6 so it opens a new block, and [9,12] extends it to [8,12]. Result: [[1, 6], [8, 12]]. The sort costs O(n log n) and dominates; the merge itself is a single linear pass. Note the max: a fully nested interval like [2, 4] inside [1, 6] must not shrink the end back to 4, and that one call is what keeps you honest.

The intervals 1-3, 2-6, 8-10 and 9-12 drawn on a number line; sorting by start makes overlaps happen only between neighbours, so 1-3 and 2-6 fuse into 1-6 and 8-10 and 9-12 fuse into 8-12, giving the merged result 1-6 and 8-12.

In the wild: coalescing free memory

A memory allocator lives and dies by this pattern. As a program frees blocks, the allocator accumulates a list of free regions, each a range of addresses. If it never merged them, freeing a megabyte one kilobyte at a time would leave a thousand tiny useless holes and the next large request would fail even though the space exists. So the allocator coalesces: whenever freed regions are adjacent or overlapping, it fuses them into one larger free block.

def coalesce(blocks):
    # blocks are (start_address, end_address)
    blocks.sort(key=lambda b: b[0])
    free = [list(blocks[0])]
    for start, end in blocks[1:]:
        last = free[-1]
        if start <= last[1]:               # touching or overlapping, fuse them
            last[1] = max(last[1], end)
        else:
            free.append([start, end])
    return free

It is exactly the calendar problem wearing a hardware costume: a set of ranges, merged into maximal non-overlapping ones by one sorted pass. The only wrinkle worth noticing is the touching case. Two blocks where one ends precisely where the next begins are not "overlapping" in the strict sense, but for memory they absolutely should fuse into contiguous space, which is why the comparison is <= and not <. That choice, whether adjacency counts as overlap, is the single most important decision in any interval-merge, and here the real world makes it for you.

The trigger

You have a collection of ranges (times, addresses, numeric spans) and you want to combine, count, or reason about the ones that overlap. The instant a problem is about "overlapping intervals," sort by start and think about merging neighbors. If your first instinct is comparing every interval to every other, that quadratic urge is the smell.

Where it shows up

  • Calendar and scheduling: flattening bookings to find busy or free stretches.
  • Range simplification: coalescing IP or CIDR ranges in a firewall, or free blocks in an allocator.
  • Insert and merge: dropping a new interval into an already-merged set and repairing the overlaps around it.

Where it bites

Three things trip people. Sorting by the wrong key, end instead of start, quietly breaks the neighbor-only guarantee. Forgetting the max when extending lets a nested interval shrink the block. And the <= versus < decision on touching intervals silently changes the answer, so make it on purpose, not by accident.

When it is the wrong tool

Merging is a one-shot cleanup, not a query engine. If the intervals are static and you will ask many "what overlaps this point or range" questions, do not re-merge each time; build an interval tree or a segment tree once and query it in O(log n). If intervals arrive and disappear continuously, a plain sort-and-merge forces a full rebuild on every change, and again a dynamic structure earns its keep. And if all you need is whether any two intervals overlap at all, you do not need the merged list, only a sort and one adjacent-pair check.

Its neighbors

It is the flagship application of Sorting-Based Patterns, useless without that first sort. The merge decision, extend the current block or start a new one, is a small Greedy choice made locally and never revisited. And the sorted sweep is close kin to Two Pointers, one cursor walking a single ordered sequence.

References