Interval Merging

The previous three patterns took the input as given: two pointers expected sorted order, sliding window looked at signs, fast and slow pointer followed a successor link. This lesson’s pattern rearranges the input first. Merging overlapping intervals begins by sorting the intervals by some criterion, and once sorting is done, a single pass suffices.

The precondition is no longer a property of the data; it is the criterion chosen itself. When the criterion is chosen wrongly, the pattern still finishes in a single pass, still returns a list of intervals, and still gives no warning. This lesson compares three wrong criteria against the same oracle and counts how many inputs each one merges incorrectly.

Problem, Oracle, and Pattern

The problem is this: given a set of intervals, merge the overlapping ones to produce the simplest list. The oracle does no sorting at all; whenever it finds an overlapping pair, it merges it and repeats until no pair remains. This makes the result correct by definition, but it restarts the scan from the beginning on every merge.

The pattern sorts once, then scans the list left to right: each interval either extends the last merged interval’s right end, or opens a new merged interval.

PP25. The corpus is 40 sets; each set carries 12 intervals. Start 0–60, length 1–9; seed 20260218. PP26. Intervals are closed: interval (4, 20) contains every point between 4 and 20 and overlaps (20, 25). PP27. The oracle’s and the pattern’s answers are sorted before comparison; a divergence arises not from an order difference but only from a content difference. PP28. Sorting’s step count is charged to the pattern’s account. A comparison-based procedure is used and every comparison is counted as one step; the sorting procedures themselves were measured in the Algorithms course and are not repeated here.

SEED, INTERVAL_COUNT, CORPUS_SIZE = 20260218, 12, 40


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def interval_corpus(seed=SEED, n=CORPUS_SIZE, count=INTERVAL_COUNT):
    r = generator(seed)
    items = []
    for i in range(n):
        row = []
        for _ in range(count):
            start = r(61)
            row.append((start, start + 1 + r(9)))
        items.append({"no": i + 1, "interval": row})
    return items


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def oracle_merge(intervals, s):
    """Merges an overlapping pair whenever found, repeats until no change."""
    remaining = [list(a) for a in intervals]
    changed = True
    while changed:
        changed = False
        for i in range(len(remaining)):
            for j in range(i + 1, len(remaining)):
                s.count()
                if remaining[i][0] <= remaining[j][1] and remaining[j][0] <= remaining[i][1]:
                    remaining[i] = [min(remaining[i][0], remaining[j][0]),
                                     max(remaining[i][1], remaining[j][1])]
                    remaining.pop(j)
                    changed = True
                    break
            if changed:
                break
    return sorted(tuple(a) for a in remaining)


def sort_counting(items, key, s):
    a = list(items)
    for i in range(1, len(a)):
        j = i
        while j > 0:
            s.count()
            if key(a[j - 1]) <= key(a[j]):
                break
            a[j - 1], a[j] = a[j], a[j - 1]
            j -= 1
    return a


def pattern_merge(intervals, key, s):
    """PRECONDITION: sort key must be START. A single pass suffices."""
    result = []
    for start, end in sort_counting(intervals, key, s):
        s.count()
        if result and start <= result[-1][1]:
            result[-1] = (result[-1][0], max(result[-1][1], end))
        else:
            result.append((start, end))
    return sorted(result)


CRITERIA = (("by start   ", lambda a: a[0]),
            ("by end     ", lambda a: a[1]),
            ("by length  ", lambda a: a[1] - a[0]),
            ("unsorted   ", lambda a: 0))

K = interval_corpus()
print("corpus:", len(K), "sets x", INTERVAL_COUNT, "intervals")
print("criterion         diverging/40  pattern  oracle   ratio   first diverging")
for ad, key in CRITERIA:
    diverging, pk, ok = [], 0, 0
    for k in K:
        s1, s2 = Counter(), Counter()
        a = pattern_merge(k["interval"], key, s1)
        b = oracle_merge(k["interval"], s2)
        pk, ok = pk + s1.step, ok + s2.step
        if a != b:
            diverging.append(k["no"])
    print(f"{ad}  {len(diverging):8d}  {pk:5d}  {ok:5d}  {ok / pk:5.2f}"
          f"   {diverging[:5]}")

corpus: 40 sets x 12 intervals
criterion         diverging/40  pattern  oracle   ratio   first diverging
by start            0   2154   2974   1.38   []
by end             29   2145   2974   1.39   [2, 3, 4, 6, 7]
by length          40   2041   2974   1.46   [1, 2, 3, 4, 5]
unsorted           40    920   2974   3.23   [1, 2, 3, 4, 5]

Four rows, four separate criteria, the same oracle, the same corpus. Only the first row is correct: the pattern sorted by start produces the same list as the oracle on 40 of 40 inputs.

The last row is this lesson’s sharpest number. The unsorted pattern is the fastest — 920 steps, ratio 3.23 — and wrong on 40 of 40 inputs. Skipping sorting makes the pattern three times faster and breaks it entirely. Sorting’s step count can be read directly: the 1234 steps between 2154 and 920 are the cost of establishing the precondition, and they eat the largest share of the pattern’s gain.

The oracle’s 2974 steps also need explaining. The oracle restarts the scan from the beginning after every merge, because the newly formed wide interval might overlap a pair already checked. This is a deliberately expensive choice, and its purpose is not speed but never missing an overlap. That the pattern gives the same result in a single pass comes from sorting making this restart unnecessary: in a list sorted by start, no later interval can touch a merged interval that has already closed.

The gap between the two middle rows is also instructive. Sorting by length is wrong on 40 of 40 inputs; sorting by end is wrong on 29. Both are the wrong criterion, but one produces the correct answer on a quarter of inputs — and that quarter is enough for the criterion to be mistaken for correct.

Why Sorting by End Breaks the Merge

The pattern’s only decision rule is the comparison start <= result[-1][1]: merge if the new interval’s start does not go past the open merged interval’s right end. This rule assumes that every subsequent interval’s start is not smaller than the previous one’s. Sorting by start guarantees exactly this.

When sorted by end, an interval that starts late but ends early can move ahead; the interval following it, which starts earlier, no longer satisfies the merge condition and opens a new merged interval. Two records that contain one another remain in the result list.

def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def interval_corpus(seed, n=40, count=12):
    r = generator(seed)
    items = []
    for i in range(n):
        row = []
        for _ in range(count):
            start = r(61)
            row.append((start, start + 1 + r(9)))
        items.append({"no": i + 1, "interval": row})
    return items


def oracle_merge(intervals):
    remaining = [list(a) for a in intervals]
    changed = True
    while changed:
        changed = False
        for i in range(len(remaining)):
            for j in range(i + 1, len(remaining)):
                if remaining[i][0] <= remaining[j][1] and remaining[j][0] <= remaining[i][1]:
                    remaining[i] = [min(remaining[i][0], remaining[j][0]),
                                     max(remaining[i][1], remaining[j][1])]
                    remaining.pop(j)
                    changed = True
                    break
            if changed:
                break
    return sorted(tuple(a) for a in remaining)


def pattern_merge(intervals, key):
    result = []
    for start, end in sorted(intervals, key=key):
        if result and start <= result[-1][1]:
            result[-1] = (result[-1][0], max(result[-1][1], end))
        else:
            result.append((start, end))
    return sorted(result)


small = [(4, 20), (6, 8), (10, 12)]
print("small example       :", small)
print("  oracle             :", oracle_merge(small))
print("  by start            :", pattern_merge(small, lambda a: a[0]))
print("  by end              :", pattern_merge(small, lambda a: a[1]),
      "  <- sorted by end:", sorted(small, key=lambda a: a[1]))
print()
print("seed       criterion         diverging/40   ratio")
for seed in (20260218, 20260219):
    K = interval_corpus(seed)
    for ad, key in (("by start   ", lambda a: a[0]),
                    ("by end     ", lambda a: a[1]),
                    ("by length  ", lambda a: a[1] - a[0]),
                    ("unsorted   ", lambda a: 0)):
        diverging = sum(1 for k in K
                        if pattern_merge(k["interval"], key)
                        != oracle_merge(k["interval"]))
        print(f"{seed}  {ad}  {diverging:8d}   {diverging / 40:.4f}")

small example       : [(4, 20), (6, 8), (10, 12)]
  oracle             : [(4, 20)]
  by start            : [(4, 20)]
  by end              : [(6, 8), (10, 20)]   <- sorted by end: [(6, 8), (10, 12), (4, 20)]

seed       criterion         diverging/40   ratio
20260218  by start            0   0.0000
20260218  by end             29   0.7250
20260218  by length          40   1.0000
20260218  unsorted           40   1.0000
20260219  by start            0   0.0000
20260219  by end             32   0.8000
20260219  by length          40   1.0000
20260219  unsorted           40   1.0000

The three-interval small example shows the whole mechanism at once. The correct answer is a single interval: (6, 8) and (10, 12) are entirely contained in (4, 20). Sorted by end, (4, 20) falls to the end of the list; the pattern starts with (6, 8), (10, 12) does not merge and opens a new record, then (4, 20) arrives and turns it into (10, 20). What remains is (6, 8), standing apart even though it is contained.

PP29. The second corpus comes from seed 20260219. Diverging inputs sorted by end are 32/40, versus 29/40 in the first; ratios 0.7250 and 0.8000, the same order of magnitude. The result does not depend on the corpus. Sorting by length and not sorting give 40/40 in both corpora.

The Criterion Is Not Just the Key, It Is the Tie Rule

Once a sort criterion is chosen, one more question remains and is often left unasked: which order do two records with the same value come in. A second interval problem makes this question measurable: at a given point, how many intervals are open at once, at most.

The pattern turns intervals into events — every start an opening, every end a closing — and sorts the events by coordinate to count them in a single pass. If one interval ends at the same coordinate where another begins, the closing must be processed before the opening; counting an already-closed end twice inflates the open-interval count.

PP30. In this measurement intervals are half-open: an interval contains its start but not its end. The oracle counts, at every start point, exactly how many intervals are open. PP31. In 32 of the corpus’s sets, one interval’s end coincides with another’s start; the tie rule’s effect can only be seen in these sets.

def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def interval_corpus(seed=20260218, n=40, count=12):
    r = generator(seed)
    items = []
    for i in range(n):
        row = []
        for _ in range(count):
            start = r(61)
            row.append((start, start + 1 + r(9)))
        items.append({"no": i + 1, "interval": row})
    return items


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def oracle_overlap(intervals, s):
    """How many intervals are open at every start point. Every pair is tried."""
    most = 0
    for start, _ in intervals:
        open_count = 0
        for b, e in intervals:
            s.count()
            if b <= start < e:
                open_count += 1
        most = max(most, open_count)
    return most


def pattern_overlap(intervals, end_first, s):
    """PRECONDITION: an END event at the same coordinate must be processed before a START."""
    event = []
    for start, end in intervals:
        event.append((start, 1 if end_first else 0, +1))
        event.append((end, 0 if end_first else 1, -1))
    most = open_count = 0
    for _, _, delta in sorted(event):
        s.count()
        open_count += delta
        most = max(most, open_count)
    return most


K = interval_corpus()
tied = sum(1 for k in K
           if {b for b, _ in k["interval"]} & {e for _, e in k["interval"]})
print("corpus: 40 sets x 12 intervals | an end tied to a start in:", tied)
print("event order     diverging/40  pattern  oracle   ratio   first diverging")
for ad, end_first in (("end first    ", True), ("start first  ", False)):
    diverging, pk, ok = [], 0, 0
    for k in K:
        s1, s2 = Counter(), Counter()
        a = pattern_overlap(k["interval"], end_first, s1)
        b = oracle_overlap(k["interval"], s2)
        pk, ok = pk + s1.step, ok + s2.step
        if a != b:
            diverging.append(k["no"])
    print(f"{ad}  {len(diverging):10d}  {pk:5d}  {ok:5d}  {ok / pk:5.2f}"
          f"   {diverging[:5]}")

corpus: 40 sets x 12 intervals | an end tied to a start in: 32
event order     diverging/40  pattern  oracle   ratio   first diverging
end first               0    960   5760   6.00   []
start first             8    960   5760   6.00   [5, 7, 8, 15, 31]

The step columns of both rows are identical: pattern 960, oracle 5760, ratio 6.00. The only thing that changes is which of two events at the same coordinate is processed first, and that single decision changes the answer on 8 inputs.

The number eight is less than a quarter of 32, and this explains why the criterion goes unnoticed. In the 8 sets with no coincidence, the tie rule has no effect at all; in most of the 32 sets with a coincidence, the answer does not change because the widest overlap occurs somewhere else. The rule only shows up on 8 inputs — but on those 8 it is wrong, and which 8 they are is knowable only through the oracle.

Three Numbers

Metric	Oracle	Pattern	Diverging input
Sorted by start	2974 steps	2154 steps	0/40
Sorted by end	2974 steps	2145 steps	29/40
Unsorted	2974 steps	920 steps	40/40
Overlap count, end first	5760 steps	960 steps	0/40
Overlap count, start first	5760 steps	960 steps	8/40

In none of the five rows does the step column carry information about correctness; in the third row the lowest step count and the highest wrong-answer count sit together. The pattern’s precondition can be stated in one sentence: the sort key must guarantee exactly what the pattern’s single decision rule assumes — no more, no less. Choosing the criterion by looking at a field that “seems natural” is choosing without looking at the decision rule.

Summary

• Interval merging is the first pattern that sorts the input beforehand; its precondition is a property not of the data but of the chosen criterion.
• Sorting by start is correct on 40 of 40 inputs; sorting by end diverges from the oracle on 29, sorting by length and not sorting diverge on 40.
• Skipping sorting drops the pattern from 2154 to 920 steps and breaks it on all inputs; the fastest row is the most broken row.
• In the second corpus, diverging inputs sorted by end are 32; because the ratio holds its order of magnitude, the result does not depend on the corpus.
• In the overlap count, event order at the same coordinate alone changes the answer on 8 inputs; step count stays exactly the same in both cases.

Next Step

This pattern paid the cost of sorting and got a single pass in return. The next pattern skips sorting entirely: in a range where values know their own position, each value is placed directly at its destination, with no comparison at all. Its precondition is heavy — the values must lie between 1 and n and contain no duplicates — and when it breaks, the pattern does not just give a wrong answer, it spins without stopping. The next lesson counts these two defects separately.