Why does cancelling the fewest conflicting ad slots reduce to keeping the earliest-ending ones?

## The two framings are one problem A broadcast day has `n` proposed ad slots with start and end times, and some overlap. You must end up with a conflict-free lineup while cancelling as few slots as possible. The move that makes this easy is noticing that every slot ends up in exactly one of two buckets — kept or cancelled — so `cancelled = n - kept`. Minimizing the left side is identical to maximizing the right side, and maximizing the kept conflict-free set is precisely maximum activity selection. **You do not need a removal algorithm; you need the selection algorithm and a subtraction.** Candidates who miss this go hunting for a bespoke deletion heuristic — remove the slot with the most conflicts, remove the longest slot, remove slots until nothing overlaps — and end up with something slower and unproven. Recognizing the complement is most of the value of this question. ## The local rule and why it is the same rule Run the sweep in end-time order, holding the finish time of the last kept slot. When the current slot starts before that finish, the two conflict and one of them must go. **Always cancel the one that ends later.** Because the list is sorted by end time, the later-ending one of the pair is the current slot, so the sweep simply skips it — which is why the removal loop and the selection loop are textually almost identical. The justification is the same one-liner that powers earliest-finish selection: the only thing a kept slot costs the rest of the day is the moment the airtime becomes free again. Between two slots that cannot both survive, keeping the one that frees the airtime sooner is never worse and is often strictly better. Concretely, if `09:00-12:00` conflicts with `11:00-11:30`, cancel the three-hour slot: keeping `11:00-11:30` frees the day at 11:30 and may admit another slot at noon, whereas keeping `09:00-12:00` blocks everything until midday. The instinct to cancel the *later-starting* slot, or the *shorter* one because it "costs less," is the classic wrong answer and it loses slots on exactly this shape of input. ## The counting trap The second common failure is arithmetic rather than algorithmic. Given five slots that mutually overlap — say five thirty-minute spots all crammed into the same half hour — a candidate counts conflicting *pairs*. There are ten. But cancelling four slots resolves all ten pairs at once, because a conflict needs two survivors and there is only one survivor left. In general a group of `k` mutually overlapping slots costs `k - 1` cancellations, not `k(k-1)/2`, and not `k`. Conflicts are a property of pairs; the thing you are minimizing is a count of slots. Keeping those two units straight is what the question is really testing. ## Cost and shape ``` sorted by end time ascending cancelled = 0 lastEnd = -infinity for each slot in sorted order: if slot.start conflicts with lastEnd: cancelled = cancelled + 1 // drop this one: it ends later else: lastEnd = slot.end ``` One sort plus one linear pass: `O(n log n)` time, `O(1)` auxiliary state beyond the sort. Nothing about the minimization framing changes the complexity, because it *is* the maximization. ## What the answer is and is not The **number** of cancellations is unique — it is `n` minus the maximum kept size, and that maximum is well defined. The **set** of cancelled slots generally is not. With `09:00-10:00` and `09:30-10:00` overlapping and nothing else at stake, either can be the one dropped. If a product owner asks "which ads got cancelled," the honest answer is that the algorithm guarantees a minimum count and any tie-breaking among equal-cost choices is a policy decision — advertiser priority, revenue, contractual guarantees — that has to be stated as a rule, not left to whatever order the sort happened to produce. Left unstated, this is a real source of non-deterministic behaviour between runs and between environments. ## A related but distinct variant A close cousin asks for the fewest *insertion points* rather than the fewest removals: place as few inspection probes as possible so that every maintenance window contains at least one probe. That one is also solved by sorting on end times — put a probe at the earliest end, discard every window it lands inside, repeat — and the number of probes needed equals the size of the largest set of pairwise-disjoint windows. Recognizing that both the removal and the stabbing question orbit the same sorted-by-end argument is the payoff for learning the family rather than the individual problems.