1474. The First Position Nobody Watches

A corridor has whole positions from L to R inclusive. n cameras are installed; camera i watches the CLOSED range [a, b] with a <= b, so both endpoints are watched. Cameras may overlap, repeat, and reach outside the corridor.

Print the SMALLEST whole position in [L, R] that no camera watches, or the word covered if every position is watched.

L=1, R=5, [1,2] [3,4] [5,6] -> covered L=1, R=5, [1,2] [4,5] -> 3 L=2, R=4, [2,2] [4,4] -> 3

The first line is the one to study. [1,2] and [3,4] do not overlap and do not share a position, and yet nothing between them is missed, because there is no whole number strictly between 2 and 3. Adjacency over the integers is not the same as overlap, and this problem is about the positions rather than about the intervals.

## What most people try first

An array of flags indexed by position. That is correct and it is what problem 723 does, where positions run only to 2000. Here they run to 10^9 in both directions, so the array would need 2 * 10^9 entries.

The second reflex is, for each position from L upward, to scan every camera. That is O(n) per position and there are up to 2 * 10^9 positions.

## Sort by start, then push a frontier

sort the cameras by a, ascending cur = L everything from L to cur - 1 is watched for each camera [a, b] in order: if a > cur: stop a hole begins at cur cur = max(cur, b + 1) if cur > R: stop answer = "covered" if cur > R else cur

O(n log n) for the sort and one pass after it.

## Why the frontier is enough

Read cur as "the smallest position not yet known to be watched". Cameras are visited in increasing order of start, so when a camera with a > cur is reached, every camera already seen ended before cur, and every camera still to come starts at a > cur or later. Nothing watches cur, and the answer is cur.

If instead a <= cur, the camera watches from a through b, which includes cur when b >= cur and is irrelevant when b < cur. Taking cur = max(cur, b + 1) covers both cases and never moves the frontier backwards, which is what a camera nested inside an earlier one would otherwise do.

## The boundary that breaks a careless implementation

b + 1, not b. The range is closed, so a camera reaching b leaves the frontier at the next position. Writing cur = max(cur, b) reports b itself as unwatched on an input like L=0, R=0 with one camera [0, 0].

The test for a hole is a > cur, strict. A camera starting exactly at cur watches it, and a camera starting at cur + 1 does not.

And the frontier starts at L, not at the first camera's start, or a hole before every camera is missed.

## Overflow

b + 1 reaches 1000000001, inside the 2147483647 a signed 32 bit integer holds, and nothing is summed. So 32 bit arithmetic is enough, which is worth knowing precisely rather than widening by reflex.

## Related

Problem 723 asks the same question over a window bounded by 2000, where a plain difference array over every position is the intended solution and prints 0 rather than a word when the window is covered. This one has an axis 2 * 10^9 wide, so the answer has to come from the cameras themselves. Problem 1441 counts how many positions are watched, and problem 1446 reports every free stretch rather than the first free position.

Constraints - `-10^9 ≤ L ≤ R ≤ 10^9` - `1 ≤ n ≤ 200000` - `-10^9 ≤ a ≤ b ≤ 10^9` - each camera watches the closed range `[a, b]` over the whole positions, so `a == b` watches one position - cameras may overlap, repeat, and lie partly or wholly outside `[L, R]`