461. Fewest Taps for the Garden

A garden stretches from 0 to n. At each integer point i there is a tap with range r[i], which waters the closed interval [i - r[i], i + r[i]]. A range of 0 means the tap does nothing.

Print the fewest taps that together water the whole garden, or -1 if it cannot be done.

n = 5, r = 3 4 1 1 0 0 -> 1 the tap at 1 covers -3 to 5

Turning each tap into an interval makes this interval covering, and the shape is worth recognising because the greedy for it is specific.

Reduce each tap to [max(0, i - r), min(n, i + r)] and, for each left endpoint, keep only the furthest right endpoint, since a shorter interval starting at the same place is never useful.

Then sweep:

covered = 0, reach = 0, count = 0 while covered < n: extend reach to the furthest right endpoint of any interval starting at or before covered if reach did not pass covered: return -1 count++, covered = reach

The failure test is the part people omit. If no interval starting within the covered prefix reaches beyond it, there is a gap and no set of taps can close it, so the answer is -1 rather than a loop that never terminates.

Note the intervals are CLOSED, so a tap ending exactly where the next begins is enough, and the garden is an interval of length n rather than n + 1 points.

Constraints - `1 ≤ n ≤ 10000` - `0 ≤ r[i] ≤ 100`