1476. Cancelling the Fewest to Stay Under the Limit

n roadworks are planned on a road whose whole positions run from 0 to 2000. Roadwork i blocks the CLOSED range [a, b] with a <= b, so both endpoints are blocked. The council allows at most c roadworks to block any single position.

Print the fewest roadworks that must be CANCELLED so that no position is blocked by more than c of the survivors.

c=2, [1,5] [2,6] [8,9] [3,4] -> 1 c=1, [1,3] [3,5] [5,7] -> 1 c=2, [1,3] [3,5] [5,7] -> 0

The second and third lines are the convention. [1,3] and [3,5] both block position 3, and [3,5] and [5,7] both block position 5, so at c = 1 one of them has to go, and cancelling the middle one fixes both places at once. At c = 2 nothing is over the limit. Under a HALF-OPEN reading those three would never share a position and the answer would be 0 in both cases.

## What most people try first

Cancelling, at each overloaded position, the roadwork that ENDS SOONEST. It sounds like the activity-selection rule and it is the wrong way round here. On [1,3] [3,5] [5,7] with c = 1, position 3 is overloaded and the earliest-ending roadwork there is [1,3], so it goes; then position 5 is overloaded and [3,5] goes: two cancellations where one is enough. That input is in the tests, and so is [0,10] [0,1] [2,3] at c = 1, where the same rule gives 2 against an answer of 1.

The second reflex is to try every subset, which is 2^n and hopeless at n = 2000.

## Sweep left to right, and cancel the one that reaches FURTHEST

sort the roadworks by a, ascending active = empty cancelled = 0 for x from 0 to 2000: add every roadwork with a == x to active drop from active every roadwork with b < x it is behind us while |active| > c: remove from active the roadwork with the largest b cancelled += 1

With n and the axis both bounded by about 2000, recomputing the active list and scanning it for the largest b costs O(n) per position, so the whole thing is O(n * 2000), about 4 * 10^6 steps.

## Why cancelling the furthest-reaching one is optimal

Two halves.

First, nothing is cancelled unnecessarily. The loop fires only when c + 1 roadworks block the position x at once. Any valid plan must cancel at least one of those c + 1, so every cancellation the sweep makes is forced.

Second, cancelling the one reaching furthest is at least as good as cancelling any other. Let f be the active roadwork with the largest b and let g be any other active one. Both block x, so both start at or before x. Every position blocked by g from x onwards is at most b_g <= b_f, and is at least x, so it is blocked by f as well. In other words, from x onwards f blocks everything g blocks and possibly more. Take any valid plan that cancels g and keeps f; swapping the two leaves the load at or below the limit everywhere from x onwards, and before x nothing changes because the sweep has already made those positions legal. So there is an optimal plan that cancels f, and induction finishes it.

The positions before x really are settled: the sweep never adds a roadwork that could raise the load at a position it has already passed, since roadworks are added at their start.

## The boundary that breaks a careless implementation

A roadwork leaves the active set when b < x, not when b <= x, because the range is closed and it still blocks position b. Dropping it one position early is what turns the second sample into an answer of 0.

The load only ever rises at a start, so testing only at positions where something begins would also work; sweeping every position from 0 to 2000 is simpler and, at this scale, free.

## Overflow

Positions reach 2000, the answer is at most n = 2000, and nothing is summed. A signed 32 bit integer, limit 2147483647, holds everything with enormous room to spare.

## Related

Problem 1437 is the case c = 1 on a much wider axis and under the convention that touching does NOT overlap, and it is solved by the mirror-image greedy: sort by END and keep the earliest-finishing, which is the same exchange argument seen from the other side. Problem 1448 asks how far over the limit the load gets without cancelling anything.

Constraints - `1 ≤ n ≤ 2000` - `1 ≤ c ≤ n` - `0 ≤ a ≤ b ≤ 2000` - each roadwork blocks the closed range `[a, b]`, so both endpoints count and `a == b` blocks one position - roadworks arrive in no particular order and may repeat