462. Fewest Clips to Cover
Clips each cover a half-open interval [start, end) of a recording. Print the
fewest clips needed to cover [0, T) completely, or -1 if it cannot be done.
Clips may overlap, may be used or skipped freely, and may extend beyond T.
T = 10, clips (0,2) (8,10) (1,9) (1,5) (5,9) -> 3
Problem 461 is the same covering problem with the intervals derived from tap ranges. This one gives them directly, which makes the shared structure visible: both reduce to "cover a line segment with the fewest given intervals", and both are solved by the same sweep rather than by a table.
covered = 0, reach = 0, count = 0
while covered < T:
reach = furthest end among clips whose start <= covered
if reach <= covered: return -1
count++, covered = reach
The rule to internalise is that among all clips usable right now, the correct choice is the one reaching FURTHEST, never the one starting earliest or the longest one. Reaching furthest maximises what is usable on the next step and gives up nothing, which is an exchange argument identical to problem 457's.
Because the intervals are half-open, a clip ending at x and one starting at x
join with no gap, and (0,1) (1,5) covers [0,5) in two. A closed-interval reading
would make that three, which is why the statement is explicit.
Constraints - `1 ≤ T ≤ 100000` - `1 ≤ k ≤ 100000` - `0 ≤ start < end ≤ 200000`
Input
The first line contains two integers T and k.
Each of the next k lines contains two integers: the start and the end of one clip.
Output
Print the fewest clips needed to cover [0, T), or -1 if it is impossible.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.