skip to content

When merging sorted intervals, why extend with max(end, next.end) instead of next.end?

level: middleimportance: must knowfreq 70%

answer

  1. sorting orders starts, not ends
  2. what if one slot sits inside another
  3. the end must never move backwards
  4. furthest end seen in this run
  5. containment stops being a special case

basics

~20 s

Sorting by start does not order the ends, so the next interval can be fully contained in the open one. Assigning next.end there truncates coverage that the input actually had; max keeps the furthest end seen and handles containment with no special case.

solid answer

~40 s

Sorting by start says nothing about ends: `[09:00, 18:00]` can be followed by `[12:00, 12:30]`, a slot entirely inside it. If the extension step assigns the incoming end, the open interval shrinks from 18:00 to 12:30 and the afternoon silently stops being busy — data loss with no error anywhere. Taking `max` encodes the real invariant: the open interval's end is the **furthest end among all intervals merged into it so far**, which is monotone by construction. That single `max` is also why containment needs no branch of its own; a contained interval simply fails to move the maximum. The bug survives most fixtures because hand-written examples tend to use staircase intervals where each end genuinely is later, so the two formulations agree. A containment pair is the probe that separates them.

code

pseudocode · 10 lines
pseudocode
sort a ascending by a[i].start
k = 0
out[0] = a[0]
for i in 1..length(a)-1
    if a[i].start <= out[k].end
        out[k].end = max(out[k].end, a[i].end)
    else
        k = k + 1
        out[k] = a[i]
return out[0..k]

go deeper

for a junior

Remember that the merged end is the furthest end seen so far, not the latest one seen. Be ready to give the containment example: a long block followed by a short one inside it.

for a middle

Explain why sorting by start leaves ends unordered, and state the accumulator invariant in one sentence. Show that containment needs no branch because max already covers it.

for a senior

Demonstrate how you would catch this in review and in tests: read the extension line first, demand a containment fixture, and add a total-covered-length property assertion that fails on any truncation.

for a principal

Frame it as a class of defect, not one line: silent under-coverage in a scan that folds a run into an accumulator. Argue for property-based invariants over example fixtures wherever data loss can be silent.

## The one line that carries the invariant A sort-by-start merge has only two branches. Either the incoming interval reaches the open one, in which case the open interval is extended, or it does not, in which case the open one is closed and the incoming one becomes open. Everything subtle about the algorithm lives in the extension step. The open interval's end must always mean: *the furthest point covered by any interval merged into this run so far.* Written as `end = max(end, next.end)`, that meaning is maintained by construction — the value only ever moves forward. Written as `end = next.end`, it silently changes meaning to *the end of the most recently seen interval*, which is not the same thing and is not monotone. ## Why sorting by start does not save you The assignment form is correct whenever the ends happen to be non-decreasing too. It is tempting to believe sorting delivers that, and it does not. Sorting orders one coordinate; the other is free. A calendar's busy slots make this concrete: an all-day block `[09:00, 18:00]` sorts before a lunch slot `[12:00, 12:30]` because 09:00 precedes 12:00, yet the lunch slot ends six hours earlier. This is the **containment** case: one interval entirely inside another. With `max`, the lunch slot is absorbed and changes nothing — 18:00 stays. With the assignment, the open interval becomes `[09:00, 12:30]`, and everything from 12:30 to 18:00 is reported free when it is not. Nothing throws. The output is still sorted, still disjoint, still plausible-looking; it just covers less than the input did. Silent under-coverage is the worst class of bug in a free/busy service, because the next step is to book a meeting on top of an existing one. ## Containment is not a special case, it is the absence of one A common instinct on discovering the bug is to add a branch: *if the incoming interval is contained, skip it.* That branch is redundant. "Contained" means `next.end <= end`, which is exactly the condition under which `max` returns the current end. The three situations the merge can be in — extension, containment, and disjointness — collapse into two branches precisely because `max` is used: | Relationship of incoming to open | Test `next.start <= end` | Effect of `max` | |---|---|---| | Extends past the open end | true | end moves forward to `next.end` | | Fully contained inside the open one | true | end unchanged | | Starts after the open end | false | open interval closed, new one opened | Adding an explicit containment branch adds a path to test and a place for the two conditions to drift apart during a later edit. The `max` is the more robust encoding of the same logic. ## Spotting it in review Because the two formulations agree on staircase data, this defect survives eyeballing and it survives most fixtures. Three review habits catch it: 1. **Read the extension line first.** In a merge routine it is the highest-value line in the diff. If it is an assignment rather than a maximum, ask for the containment test immediately. 2. **Demand a containment fixture by name.** A long range followed by a short one nested inside it, asserting the merged end equals the long range's end. One case, three lines, permanently pins the behaviour. 3. **Assert a total-coverage property.** The summed length of the output must equal the length of the union of the input. Truncation always shrinks that number, so a randomized property test catches the bug even without anyone thinking about containment specifically. ## Related places the same mistake appears The same monotone-accumulator shape shows up in any single-pass scan that folds a run of items into one summary: a running furthest-reach, a maximum-so-far, a watermark. The rule to internalise is that when a scan maintains "the best value seen in this run", the update must be a `max` (or `min`) over the accumulator and the new item, never a plain assignment of the new item — the moment the input is not monotone in that coordinate, assignment loses information. One more precision point: the reverse mistake, `end = max(end, next.start)`, is also wrong and harder to see, since it agrees with the correct rule on every pair where the incoming interval is a single point or where its start already exceeds the accumulated end. Read the operands as carefully as the operator.

  • Write the one test input that fails with assignment and passes with max.
    Two intervals where the second is contained in the first: `[09:00, 18:00]` then `[12:00, 12:30]`. Expected output is the single interval `[09:00, 18:00]`. With the assignment form the result is `[09:00, 12:30]`, losing five and a half hours of coverage. Any staircase input — each interval ending later than the last — passes under both formulations, which is why fixtures written by hand almost never catch this.
  • Should you add an explicit branch for the contained case?
    No. Containment means `next.end <= end`, which is precisely when `max` returns the unchanged end, so the branch is dead weight that duplicates a condition already expressed. It adds an untested path and a chance for the two conditions to drift apart in a later edit. The two-branch form with `max` handles extension, containment and disjointness completely.
  • What single property assertion would have caught this in a randomized test?
    Total covered length. Sum the lengths of the output intervals and compare against the length of the union of the inputs computed independently — for instance by a brute-force point or boundary count on small random cases. Truncation always shrinks the covered total, so the property fails loudly on random inputs even when no one thought to write a containment fixture.

It is a high-water mark on a harbour wall. You paint over the old line only when the tide comes in higher, never because the latest tide was lower.

saying these in an interview costs you the question

  • Assumes sorted starts imply sorted ends
  • Adds a special branch for contained intervals
  • Says max is defensive coding, not correctness
  • Cannot name an input where the two forms differ
  • Thinks the bug would throw or be visibly wrong

context

resolving links…