1450. How Long at Least k Machines Are Busy

n machines each run once. Machine i is busy over the HALF-OPEN stretch [a, b) with a < b, so a machine finishing at t and one starting at t are never busy together.

Given k, print the total LENGTH of time during which at least k machines are busy simultaneously.

n=4, k=2, [1,5) [2,6) [8,9) [3,4) -> 3 two or more are busy over [2,5) n=3, k=1, [1,3) [3,5) [5,7) -> 6 one unbroken busy stretch n=3, k=2, [1,3) [3,5) [5,7) -> 0 never two at once

Work the first line out for yourself. One machine is busy over [1,2), two over [2,3), three over [3,4), two over [4,5), and one from 5 onwards. Two or more are therefore busy over [2,5), which is 3. It is the LENGTH OF THE UNION that is wanted, not the sum of the stretches at each level: adding the stretch at level two to the stretch at level three would count [3,4) twice.

Lines two and three are the endpoint rule. The three machines hand over cleanly, so at least one is busy for the whole of [1,7), six units, and two are never busy together at all.

## What most people try first

Walking time one unit at a time and counting. Coordinates reach 10^9 in both directions, so that is up to 2 * 10^9 steps.

The second reflex is to add up the lengths of the stretches where each PAIR overlaps. That counts a stretch covered by three machines three times, and it is O(n^2) besides.

## Sweep, and measure the gaps between events

for each machine [a, b): event(a, +1) and event(b, -1) sort by coordinate total = 0 walk the distinct coordinates in order: apply EVERY event at this coordinate x if the running count is now >= k: total += (next coordinate) - x

The running count is constant between two consecutive event coordinates, so one multiplication of "is it at least k" by "how wide is the gap" settles that whole stretch. O(n log n) for the sort, one pass after it.

## Why applying every event at a coordinate first is necessary

Several machines can start and finish at the same coordinate. Reading the count between two of those events would report a level that holds over a stretch of zero width, and adding a zero is harmless, but the count would then be wrong for the stretch that follows. Applying them as a group and only then measuring to the next coordinate keeps the count you multiply by the width the count that actually holds there.

Because the events at a coordinate are applied together, the order of a -1 and a +1 within that group does not matter here, unlike in problem 1448 where the count is read after every single event.

## The boundary that breaks a careless implementation

The last coordinate has no gap after it, so there is nothing to add there and a loop that reads next unguarded runs off the end of the array. The count is also guaranteed to be 0 at that point, since every machine that started has finished, which is a useful check on the sweep.

k may exceed n, in which case no stretch qualifies and the answer is 0.

## Overflow

The answer is at most the whole span, 2 * 10^9, which FITS in a signed 32 bit integer since the limit is 2147483647. The raw total of all machine busy times does not: 2 * 10^5 machines busy for 2 * 10^9 each reach 4 * 10^14. Accumulate in 64 bit.

## Related

Problem 1448 asks for the largest number busy at once rather than how long a level lasts. Problem 1461 asks for the widest single stretch at EXACTLY a given level, which is a different sweep because adjacent stretches at the same level must be joined. Problem 1442 is the same question for closed integer intervals with k = 1 and the level measured in whole positions.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 200000`, and `k` may be larger than `n` - `-10^9 ≤ a < b ≤ 10^9` - each machine is busy over the half-open stretch `[a, b)`, so finishing at `t` and starting at `t` do not overlap