Fewest Sprinklers to Cover the Field
A linear field stretches from 0 to n. Each sprinkler at position i wets a radius around it. Open the fewest sprinklers so the whole field is watered end to end.
Problem
There are n+1 sprinklers at positions 0..n. Sprinkler i has range ranges[i], covering the closed segment [i - ranges[i], i + ranges[i]]. Return the minimum number of sprinklers to open so that every point in [0, n] is covered, or -1 if it is impossible. A sprinkler with range 0 covers nothing.
Input
An integer n and an array ranges of length n+1 with ranges[i] >= 0.
Output
The minimum number of sprinklers, or -1 if impossible.
Constraints
- 1 <= n <= 10^4
- ranges.length == n + 1
- 0 <= ranges[i] <= 100
Examples
Example 1
Input
n = 5, ranges = [3,4,1,1,0,0]
Output
1
Sprinkler at index 1 covers [-3,5], spanning the whole field.
Example 2
Input
n = 3, ranges = [0,0,0,0]
Output
-1
No sprinkler covers any width; the field cannot be watered.