skip to content

Why does colouring overlapping reservations in start-time order need exactly as many slots as the busiest instant?

level: seniorimportance: must knowfreq 55%

answer

  1. look at the busiest instant
  2. earlier neighbours are still open
  3. pairwise overlap shares one moment
  4. peak overlap is a mutual-conflict group
  5. greedy by start reaches the floor

basics

~20 s

In start-time order a reservation meets only earlier ones still open, and those all contain its start instant, so it takes a new slot only when the overlap grows. The busiest instant is both the unavoidable floor and the count the sweep reaches.

solid answer

~40 s

Model each reservation as an interval and draw an edge between any two that overlap. Two facts meet. From below, all reservations live at one instant pairwise overlap, so they form a mutual-conflict group and force that many slots — no assignment can do better. From above, process reservations by start time and give each the lowest free slot: its already-placed conflicting neighbours are exactly the ones still open at its start, and together with it they all sit at that instant, so at most `peak − 1` slots are blocked and one of the first `peak` is free. Floor meets ceiling, so the answer is exactly the maximum number open at once, and a single sweep over sorted start and end events computes it.

code

pseudocode · 12 lines
pseudocode
events = empty list
for each reservation r:
    add (r.start, +1) to events
    add (r.end, -1) to events
sort events by time, and at equal time put -1 before +1
open = 0
peak = 0
for each (time, delta) in events:
    open = open + delta
    if open > peak:
        peak = open
return peak

go deeper

for a junior

Recall the rule of thumb: the number of rooms is the largest number of bookings open at the same moment, not the total number of bookings.

for a middle

Explain both halves — why simultaneous bookings force that many rooms, and why processing in start order never opens more.

for a senior

Show the operational judgment: define the endpoint convention explicitly, pad for setup time in the data, and say where the peak stops being the answer.

for a principal

Recognise when a conflict model can be forced into this shape. Structure that makes the bound exact is worth more than any scheduling heuristic you can buy.

## The model Each reservation is an interval on one timeline. Two reservations conflict when their intervals overlap, so the conflict graph has an edge for each overlapping pair. A slot is a colour, and "how many rooms do we need" is "what is the chromatic number of this graph". What makes this leaf's answer clean is that the conflicts are not arbitrary — they come from intervals on a line, and that geometry constrains the graph far more than an edge list would. ## The floor: the busiest instant is a mutual-conflict group Suppose `p` reservations are open at some instant `t`. Every pair of them contains `t`, so every pair overlaps, so they pairwise conflict: they are a clique of size `p`, and no schedule uses fewer than `p` rooms. The converse is the geometric fact that makes the whole argument work: **any set of intervals that pairwise overlap all share one common instant.** Take the largest left endpoint `L` among them, belonging to interval `I`. Every other interval `J` starts no later than `L` and must reach `I`, so `J` ends at or after `L`. Hence `L` lies inside every interval of the set. Consequently the largest mutual-conflict group is exactly the largest number open at one instant, and there is no hidden clique bigger than the visible peak. ## The ceiling: greedy by start time never exceeds the peak Order the reservations by start time and give each the lowest-numbered slot no conflicting, already-placed reservation holds. When reservation `R` is placed: - Its already-placed conflicting neighbours all started at or before `R.start` and have not yet ended — otherwise they would not overlap `R`. - Every one of them therefore **contains the instant `R.start`**, and so does `R`. - If there were `peak` such neighbours, then together with `R` that instant would carry `peak + 1` open reservations, contradicting the definition of the peak. - So at most `peak − 1` slots are blocked, and one of the first `peak` slots is free. The ceiling therefore equals the floor, the sweep count is the exact answer, and this greedy needs no cleverness — its optimality is bought entirely by the ordering plus the interval geometry. ## Computing the peak One pass over sorted endpoint events does it: `+1` at each start, `−1` at each end, track the running maximum. The tie rule at equal times is a modelling decision rather than a mathematical one, and it decides whether a handover counts as a clash: - Process ends before starts and a reservation finishing at `t` does **not** conflict with one beginning at `t` — the half-open reading, usually what a booking system wants. - Process starts before ends and every handover adds a phantom conflict, inflating the peak by one at each boundary. - If there is real setup or teardown cost, model it by padding the interval, not by fiddling with the tie rule — padding is visible in the data, tie-breaking is not. ## Why it does not generalise Every step above used the line. Drop it and both halves fail: - **The floor stops being tight.** Conflicts that are not derived from intervals can beat their largest mutual-conflict group — five jobs in a ring have no mutual triple and still need three slots. - **The order stops being special.** "Sort by start" has no meaning for an arbitrary conflict graph, and greedy in an unlucky order can use far more slots than necessary. So the right sentence to carry away is not "greedy colouring is optimal" but "greedy colouring is optimal **when the conflicts come from intervals on a line**, because there every pairwise-overlapping set shares one moment". ## Traps worth naming - **Counting the wrong thing.** The answer is the maximum simultaneous count, never the total number of reservations or the number of overlapping pairs. - **Confusing two problems.** Picking the most non-overlapping bookings that fit one room is a different question with a different greedy rule; this one is about covering all bookings with the fewest rooms. - **Per-room limits.** If a room holds several small bookings under an extra capacity rule, the mapping to plain colouring breaks and the peak is no longer the answer. - **More than one timeline.** Reservations on separate resources are separate graphs; merging them into one peak count silently over-provisions.

  • Does the same argument make start-order greedy optimal on any conflict graph?
    No. It relies on conflicts coming from intervals on a line, where any pairwise-overlapping set shares one instant, so the largest mutual-conflict group equals the peak. Arbitrary conflict graphs can need more slots than their largest such group — a five-job ring needs three with no mutual triple — and have no natural start order at all.
  • How does back-to-back handling change the count?
    It is a modelling choice. Treat intervals as half-open and process end events before start events at equal times, and a booking ending at t does not clash with one starting at t. Process starts first and every handover creates a phantom overlap, raising the peak by one at each boundary and over-provisioning rooms.
  • What breaks if each room may hold two small bookings at once?
    The mapping to plain colouring breaks. Colouring places no limit on how many jobs share a colour and only forbids conflicting pairs; a per-room capacity is an extra constraint outside that model. The peak overlap is then no longer the answer, and you are solving a different, more constrained problem.

saying these in an interview costs you the question

  • Counts total reservations instead of the maximum simultaneous
  • Confuses this with picking the most non-overlapping bookings
  • Says greedy is optimal because greedy is generally optimal for colouring
  • Assumes every conflict graph's slot count equals its largest clash group
  • Ignores whether a booking ending at t clashes with one starting at t