1095. Covering the Checkpoints

n checkpoints stand at given positions on a line. You are offered m patrol stretches, each a closed interval [l, r]; a stretch covers every checkpoint inside it, endpoints included.

Print the fewest stretches that together cover every checkpoint, or -1 when some checkpoint lies inside none of them.

checkpoints 1 4 7 9 12, stretches [0,5] [3,8] [6,10] [11,13] -> 3 checkpoints 1 2 3, stretches [0,10] [1,1] -> 1 checkpoints 1 9, stretches [0,3] [4,6] -> -1

Trace the first line. The leftmost checkpoint is 1. Two stretches reach it, [0,5] and, no, [3,8] starts at 3 and does not. So [0,5] is forced, and it also covers 4. The leftmost remaining checkpoint is 7; the stretches starting at or before 7 are [0,5], [3,8] and [6,10], and the one reaching furthest is [6,10], which covers 7 and 9. The last checkpoint 12 needs [11,13]. Three stretches.

## What most people try first

Taking the LONGEST stretch first. That is a plausible rule and it is wrong. With checkpoints 0 and 5 and stretches [0,4] and [0,0] and [5,5], the longest is [0,4], and two more are then needed for nothing gained, while [0,0] and [5,5] answer 2 directly. Length is not what matters; how far right a stretch reaches from the current frontier is.

Trying every subset is exact and impossible: 2^m with m up to 200000.

## The method

sort the checkpoints ascending sort the stretches by left endpoint ascending i = 0 # next uncovered checkpoint j = 0 # next unseen stretch count = 0 while i < n: best = -infinity while j < m and l[j] <= p[i]: best = max(best, r[j]) j = j + 1 if best < p[i]: answer is -1 count = count + 1 while i < n and p[i] <= best: i = i + 1

Both i and j only move forward, so after the two sorts the sweep is O(n + m).

Note that j is NOT reset between checkpoints. A stretch whose left endpoint is at or before an earlier checkpoint is also at or before a later one, so once its right endpoint has been folded into best it never needs looking at again. Resetting j turns the sweep into O(n * m), which at 200000 each is 4 * 10^10 steps.

## Why reaching furthest is the right choice

Let q be the leftmost uncovered checkpoint and let S be the set of stretches that contain q. Any solution must use at least one member of S.

Take an optimal solution and let s be the member of S it uses. Replace s by the member t of S whose right endpoint is largest. Does anything break? A checkpoint covered by s is either at or after q, in which case t covers it too since t starts at or before q and ends at or after s does, or it is before q, in which case it was already covered by something else, q being the leftmost uncovered one.

So the swap is safe and the count is unchanged. Repeat from the new leftmost uncovered checkpoint. Any optimal solution becomes the greedy one without growing, so the greedy one is optimal.

## The boundary that breaks a careless implementation

The failure test is best < p[i], and it has to be checked BEFORE the count is increased. A stretch that starts at or before p[i] but ends before it contributes a best that is too small, and a solution that only checks "were any stretches seen" counts a stretch that covers nothing and reports a number instead of -1.

Zero-width stretches, where l == r, are legal and sometimes necessary.

## Sizes

Positions reach 10^9, which is inside the 2147483647 limit of a signed 32-bit integer, and the answer is at most m. Nothing overflows here.

## Related problems

Problem #462 covers a continuous range [0, T) rather than a finite set of points, and problem #461 derives its intervals from tap ranges before running the same sweep. The difference is not cosmetic: covering points means the frontier jumps from checkpoint to checkpoint, so the failure test compares against a checkpoint rather than against the frontier itself.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ m ≤ 200000` - `0 ≤ position ≤ 1000000000` - `0 ≤ l ≤ r ≤ 1000000000`