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.