Sorting Intervals by End Before Merging

Sorted by end, a long interval that starts early arrives last and is merged into the wrong neighbour, so two intervals come out where one belongs.

Sorting intervals by end before the merge pass breaks the merge, because the pass compares each interval only with the last one merged. That shortcut is safe only when no later interval starts before the current one, which the sort by start guarantees and the sort by end does not. Sorting by end looks reasonable, since the merge tests ends, and some interval problems, such as choosing the most meetings that do not clash, do sort by end. Three intervals show the failure: [6, 7], [8, 9] and [2, 12], where [2, 12] covers both others.

text

the input
         2   4   6   8   10  12
[6, 7]           ====
[8, 9]               ====
[2, 12]  ======================

The two listings differ only in the sort key, on line 2.

The merge after sorting by end, and by start

by_end.pypy

def merge(intervals: list[list[int]]) -> list[list[int]]:
    ordered = sorted(intervals, key=lambda interval: interval[1])
    merged: list[list[int]] = []
    for start, end in ordered:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged


intervals = [[6, 7], [8, 9], [2, 12]]
print("sorted:", sorted(intervals, key=lambda interval: interval[1]))
print("merged:", merge(intervals))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

sorted: [[6, 7], [8, 9], [2, 12]]
merged: [[6, 7], [8, 12]]

by_start.pypy

def merge(intervals: list[list[int]]) -> list[list[int]]:
    ordered = sorted(intervals, key=lambda interval: interval[0])
    merged: list[list[int]] = []
    for start, end in ordered:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged


intervals = [[6, 7], [8, 9], [2, 12]]
print("sorted:", sorted(intervals, key=lambda interval: interval[0]))
print("merged:", merge(intervals))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

sorted: [[2, 12], [6, 7], [8, 9]]
merged: [[2, 12]]

Sorted by end, [2, 12] arrives last and is compared only with [8, 9], so it merges into that one, and [6, 7], already behind it, is never looked at again: two intervals come out where one belongs. Sorted by start, [2, 12] comes first and swallows both. No error is raised, and inputs where no interval contains another often come out right, which is how the slip survives a few tests. The fix is the key: interval[0].

On the Coding Interview Patterns cheatsheet

← → move through sections and cards