1451. The First Moment the Lift Is Overloaded

A lift holds c people. n riders are given; rider i is inside over the CLOSED range of floors [a, b], meaning present at every whole floor from a to b inclusive. A rider leaving at floor t and a rider entering at floor t are both counted at t.

Print the SMALLEST whole floor at which more than c riders are inside, or -1 if that never happens.

c=2, [1,5] [2,6] [8,9] [3,4] -> 3 three riders at floor 3 c=1, [1,3] [3,5] [5,7] -> 3 two riders at floor 3 c=2, [1,3] [3,5] [5,7] -> -1 never more than two

The second line is the convention. Under a HALF-OPEN reading those three riders would never share a floor and the answer would be -1, which is what the third line reports for the higher capacity. Closed means the handover floor belongs to both.

## What most people try first

An array of counters indexed by floor. That is the honest first idea and it is what problem 1439 does, where floors run only to 1000. Here they run to 10^9 in both directions, so the array would need 2 * 10^9 entries.

The second reflex is to check every floor mentioned in the input by scanning all n riders, which is O(n^2) and 4 * 10^10 at the limits.

## The difference array, carrying its own coordinates

for each rider [a, b]: event(a, +1) and event(b + 1, -1) sort by coordinate count = 0 for each distinct coordinate x, in order: apply every event at x if count > c: print x and stop print -1

This is exactly a difference array with the zeros left out: instead of an entry per floor, there is an entry per CHANGE, and the coordinate is carried alongside. O(n log n).

## Why the answer is always one of the entry floors

The count rises only at an a. So the first floor at which the count exceeds c is a floor at which somebody enters, and the sweep, which reports the first coordinate after which the count is too high, reports exactly that floor. No floor between two events needs checking, because the count there equals the count at the earlier of the two.

The b + 1 is what makes the range closed: the count must still include the rider AT floor b and drop only once past it. Writing -1 at b makes the range half-open and answers -1 on the second sample.

## The boundary that breaks a careless implementation

Every event at a coordinate must be applied before the count is tested. Two riders entering at floor 7 while one leaves at floor 6 produce three events near 7; testing after only one of them reports floor 7 as safe when it is not, or as unsafe when it is not. Group them.

c may be 0, in which case a single rider anywhere overloads the lift, and the answer is the earliest entry floor of all.

## Overflow

The largest coordinate printed is 10^9, and b + 1 reaches 1000000001, both inside the 2147483647 a signed 32 bit integer holds. The count is at most n = 200000. Nothing here needs 64 bits, which is worth noticing given how many neighbouring problems do.

## Related

Problem 1439 asks the same yes-or-no question about a vehicle with floors bounded by 1000, where a plain array of counters is the intended answer, and it uses the convention that passengers leaving at a position are off before anyone boards, which is the HALF-OPEN reading. This one is closed, reports the floor rather than a verdict, and has coordinates too wide for an array.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ c ≤ 200000` - `-10^9 ≤ a ≤ b ≤ 10^9` - each rider occupies the closed range `[a, b]`, so a rider is counted at both endpoints - `a == b` is allowed and means a rider present at a single floor