1093. Strips That Cover Every Post

Fence posts stand at n given positions along a straight line. You have tape in strips of length L. A strip laid down starting at any real position x covers the closed stretch [x, x + L], and a post lying exactly on either end counts as covered.

Print the fewest strips that cover every post.

posts 1 2 3 9, L = 3 -> 2 one strip on [1,4], one on [9,12] posts 7, L = 5 -> 1 posts 0 4 8 12 16 20, L = 4 -> 3 [0,4] [8,12] [16,20]

The third line is worth tracing, because it is where the boundary lives. A strip starting at 0 reaches exactly 4, so it covers both 0 and 4 and nothing more. The next uncovered post is 8, the strip there reaches 12, and the last strip starts at 16. Three strips, not six and not four.

## What most people try first

The usual first idea is to centre a strip on each uncovered post, so that the post sits in the middle. That wastes half a strip every time. On 0 4 8 12 16 20 with L = 4 the first strip becomes [-2, 2], which covers only the post at 0, and the answer comes out as 6 instead of 3.

The other common first idea is to try every subset of candidate start positions. With n posts there are 2^n subsets, and at n = 200000 that is not a number you can write down, let alone loop over.

## The method

Sort the positions. Then walk them once.

sort p count = 0 i = 0 while i < n: count = count + 1 reach = p[i] + L # the strip starts exactly ON this post while i < n and p[i] <= reach: i = i + 1

The inner loop never rewinds, so each post is looked at a constant number of times and the whole walk is O(n) after an O(n log n) sort.

## Why it is correct

Take any optimal set of strips and sort them by their left ends. Look at the leftmost uncovered post, call it q. Some strip in the optimal set covers q, and that strip starts at or before q.

Slide that strip right until it starts exactly at q. It still covers q, and the stretch it now covers, [q, q + L], contains every point of the old stretch that lay at or after q. No post at or after q loses its cover, and no post before q needed that strip, because q was the leftmost uncovered one. So the swapped solution is still valid and uses the same number of strips.

Repeat the swap on the next uncovered post. After finitely many swaps the optimal solution has become the greedy one without ever growing, so the greedy one is also optimal. That is the exchange argument in full, and it is the reason "start the strip on the post" beats "centre the strip on the post".

## The boundary that breaks a careless implementation

The comparison is p[i] <= reach, not <. A post sitting exactly at p[i] + L is covered, because the stretch is closed at both ends. Writing the strict comparison turns 0 4 8 12 16 20 with L = 4 from 3 into 6, and every test with evenly spaced posts catches it.

L = 0 is legal. A zero-length strip covers exactly one point, so the answer is the number of DISTINCT positions, and a solution that special-cases L = 0 is doing work the general code already does.

## Sizes

A position and L each reach 2 * 10^9. Either on its own still fits in a signed 32-bit integer, whose largest value is 2147483647, so reading the input into 32-bit variables works. Their SUM reaches 4 * 10^9, which does not fit: computed in 32 bits it wraps to a negative number, every later post then looks uncovered, and the answer comes out as the number of distinct positions. So reach needs 64 bits even though the answer is at most n and every input value would fit.

## A related problem

Problem #1095 also covers points, but there you must choose from a fixed list of stretches rather than placing your own wherever you like, and the greedy changes from "start on the post" to "among the stretches that reach this post, take the one ending furthest right".

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ L ≤ 2000000000` - `0 ≤ position ≤ 2000000000`