723. Is Every Point Covered
You are given m ranges, each a pair l r meaning every integer from l to r inclusive is
covered. You are then given a window lo hi.
Print 0 if every integer from lo to hi is covered by at least one range. Otherwise print
the SMALLEST integer in that window which no range covers.
ranges (1 2) (3 4) (5 6), window 2..5 -> 0
ranges (1 2) (4 5), window 1..5 -> 3
ranges (2 2) (4 4), window 2..4 -> 3
ranges (50 60), window 1..10 -> 1
## Overlaps make sorting the wrong first move
The instinct is to sort the ranges and merge them. That works, and it costs O(m log m).
But nothing here needs the ranges as objects at all. What is needed is, for each point, HOW MANY ranges cover it, and that is a range add of 1 followed by a sweep:
for each range: d[l] += 1; d[r + 1] -= 1
run = 0
for x in 1 .. hi:
run += d[x]
if x >= lo and run == 0: print x and stop
print 0
Counting coverage instead of merging intervals is the step worth taking away. It also leaves "how many ranges cover this point" available for free, which merging throws away.
## The sweep must start at 1, not at lo
The running total has to be correct by the time it reaches lo, and a range beginning before
lo still covers points inside the window. Starting the accumulation at lo loses every such
range and reports the first point as uncovered.
Only the TEST is restricted to the window. The accumulation is not.
## Why the smallest uncovered point needs a left-to-right scan
The answer is the first failure, so the scan stops at it. Gathering every uncovered point and taking the minimum is correct but does more work.
## Coverage is not the same as containment
A point is covered when SOME range contains it. Two ranges that touch, like 1 3 and 3 5,
leave no gap, while two that stop short, like 2 2 and 4 4, leave the single point 3
uncovered. Both are in the tests because they are what separate a coverage count from an
interval merge.
## Boundaries
A window entirely outside every range answers lo. A window of one point answers 0 or that
point.
## Cost
Time O(m + hi). Space O(hi).
Constraints - `1 ≤ m ≤ 200000` - `1 ≤ l ≤ r ≤ 2000` - `1 ≤ lo ≤ hi ≤ 2000`
Input
The first line contains three integers m, lo and hi.
Each of the next m lines contains two integers l and r.
Output
Print one integer: 0 if the window is fully covered, otherwise the smallest uncovered point.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.