skip to content

A diff flips an interval-selection guard from start >= lastEnd to start > lastEnd — what breaks?

level: seniorimportance: should knowfreq 40%

answer

  1. one character, two different specifications
  2. does an interval own its final instant
  3. which direction is silent, which double-books
  4. random test data never touches exactly
  5. pin it with a shared-instant fixture

basics

~20 s

If back-to-back items are legal, the strict comparison rejects an item starting exactly when the previous one ends, so the algorithm silently returns too few selections. Nothing crashes and most tests still pass, because only inputs with touching endpoints expose it.

solid answer

~50 s

The two guards encode opposite endpoint conventions, and only the problem statement decides which is right. Under a half-open convention — a talk ending at 14:00 does not conflict with one starting at 14:00 — `start >= lastEnd` is correct and the strict `>` **undercounts**, rejecting every legal back-to-back pair. Under a closed convention, where the endpoint itself is occupied, the directions swap and the permissive `>=` **double-books**. The failure mode matters: undercounting is a wrong answer that looks plausible; double-booking is a real conflict shipped to production. As a reviewer I would not just pick a sign — I would ask where the convention is written down, require it in the function's contract, and demand a test with two intervals touching at exactly one instant, because a suite built from randomly generated ranges almost never produces that case.

code

pseudocode · 10 lines
pseudocode
// talks sorted so that end[0] <= end[1] <= ... <= end[n-1]
// convention: a talk ending at t and one starting at t do NOT conflict
count = 0
lastEnd = -infinity
for i in 0..n-1:
    if start[i] >= lastEnd:          // flipping this to > undercounts
        count = count + 1
        lastEnd = end[i]
    ...
return count

go deeper

for a junior

Know that a talk ending at 14:00 may or may not conflict with one starting at 14:00, and that the problem statement decides. Ask which convention applies before writing the comparison.

for a middle

Explain both directions concretely: too strict rejects legal back-to-back items and returns a count that is too small, while too permissive under the opposite convention emits an actual overlap.

for a senior

Demonstrate review judgment. Say why the existing suite is blind to it, name the exact fixture that pins it, and insist the convention lives in the contract rather than in a loop nobody rereads.

for a principal

Make the convention a boundary decision, not a per-call-site one: normalize every incoming range to a single representation at the edge, so a whole class of endpoint bugs stops recurring across teams and services.

## What the guard actually encodes After sorting by end time, the selection sweep keeps one piece of state — the finish time of the last accepted interval — and one decision: does the current interval conflict with it? That single comparison carries the entire **endpoint convention** of the problem, and the convention is not a matter of taste. It is a fact about the domain that must be established before the comparison is written. Two conventions exist and both are common: - **Half-open** (`[start, end)`): the interval occupies every instant from `start` up to but not including `end`. A talk ending at 14:00 and a talk starting at 14:00 do not conflict. The correct guard is `start[i] >= lastEnd`. - **Closed** (`[start, end]`): the endpoint instant is occupied too. Those two talks *do* conflict, and the correct guard is `start[i] > lastEnd`. The diff under review changes one to the other. Nothing else in the algorithm changes — the sort key is untouched, the complexity is untouched, the structure is untouched — which is exactly why this class of change slips through review. ## The two failure directions are not symmetric Under the half-open convention, tightening to `>` makes the algorithm **too conservative**. Every back-to-back pair is treated as a conflict, so the answer is too small. The output is still a valid conflict-free selection; it is simply not maximal. Nothing throws, no invariant is violated, and downstream code happily consumes a plausible-looking number. This is the worst kind of bug to find later, because there is no signal — you discover it when someone notices the schedule has a suspicious gap at exactly the hour boundary, or when a competitor's numbers differ from yours. Under the closed convention, loosening to `>=` makes it **too permissive**, and now the algorithm produces a schedule containing a genuine conflict. Two items are booked at the same instant. If that instant is a broadcast cutover or a physical resource handover, the output is not merely suboptimal — it is wrong in a way that reaches the real world. A reviewer should say which direction applies before approving anything. The two mistakes have different blast radii, and "looks fine, off-by-one either way" is not a review. ## Why the test suite did not catch it Touching endpoints are a measure-zero case in most generated data. If test intervals come from random timestamps at second or millisecond resolution, the probability that one interval's end lands exactly on another's start is negligible, so the suite is blind to the flip. Hand-written fixtures fare little better: people write "9 to 10" and "11 to 12" because that is how humans describe a schedule, not "9 to 10" and "10 to 11". The fix in review is concrete and cheap: require a fixture with exactly two intervals sharing an instant — one ending at `t`, one starting at `t` — with the expected count spelled out in the assertion, and a comment naming the convention. That single test pins the comparison forever. ## Adjacent traps in the same neighbourhood **Granularity.** "14:00 to 15:00" at minute resolution is unambiguous, but a system storing an inclusive last-occupied minute (`14:00` through `14:59`) and another storing an exclusive end (`15:00`) will disagree about whether two records touch. Normalizing every incoming range to one convention at the parsing boundary — rather than fixing comparisons scattered through the code — is what stops this recurring. **Zero-length intervals.** An interval where `start == end` behaves differently under the two conventions: under half-open it occupies nothing and can be accepted arbitrarily often; under closed it occupies one instant. Decide whether such records are legal input, and reject them at the boundary if they are not, rather than letting the comparison decide by accident. **Ties in the sort key.** Two intervals ending at the same time do not endanger the count: whichever the sort presents first is accepted, and the other cannot be accepted afterwards because it starts before its own end, which equals the new `lastEnd`. So the total is stable under tie order even though the *chosen set* is not. Reviewers sometimes ask for a secondary sort key to "make it deterministic" — a reasonable request for reproducible output, but it should be justified as determinism, not as correctness. ## What to say as the reviewer Block the diff pending three things: the convention stated in the function's contract, a test with intervals touching at a single instant, and a one-line note in the change description saying which convention the caller uses. Then approve. The engineering point is that a strict-versus-non-strict comparison is not a style choice hidden in a loop — it is the specification, and it belongs somewhere a future reader can find without re-deriving it.

  • Which of the two wrong directions would you escalate first, and why?
    The permissive one. Under a closed convention, `>=` emits a schedule containing a real overlap, so two things are booked at the same instant and the error escapes into the world. The strict version under a half-open convention merely returns a smaller-than-maximal answer that is still internally consistent — bad, but not a live conflict.
  • What single test case pins this comparison for good?
    Two intervals sharing one instant — one ending at `t`, the next starting at `t` — with the expected selection count asserted and the convention named in the test's name or comment. Randomly generated ranges essentially never produce touching endpoints, which is precisely why this bug survives large suites.
  • Do ties in end time affect the answer?
    Not the count. If two intervals end at the same time, accepting either sets the same last-finish value, and the other necessarily starts before that value, so it is rejected. The chosen set can differ between runs while the total stays fixed. Add a secondary sort key if you want reproducible output, but justify it as determinism, not correctness.

saying these in an interview costs you the question

  • Treats strict versus non-strict as a style preference
  • Says the flip cannot change the result
  • Approves without asking which convention applies
  • Assumes the existing suite would have caught it
  • Fixes the comparison without recording the convention

context

resolving links…