Fewest Sprinklers to Cover the Whole Path
Implement fewestSprinklers
A garden path runs along a line from position 0 to position n, with a sprinkler at every whole-number position 0, 1, …, n. The sprinkler at position i can water everything within ranges[i] of itself. Every point on the path from 0 to n must be watered. Find the fewest sprinklers to switch on, or −1 if no selection can water the entire path.
Trying every set of sprinklers is exponential. But watering the path with as few overlapping stretches as possible is the same as reaching position n with as few "hops" as possible, where each sprinkler is a hop that starts at its left edge. That makes the jump-window greedy work.
Example 1:
Input: n = 8, ranges = [2,0,0,3,0,1,0,2,1]
Output: 2
Example 2:
Input: n = 1, ranges = [1,0]
Output: 1
Example 3:
Input: n = 4, ranges = [0,0,0,0,0]
Output: -1
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 10 and ranges.length = n + 1; a garden path runs along the x-axis from 0 to n, with a sprinkler at every integer position 0, 1, …, n - ●
0 ≤ ranges[i] ≤ 5; the sprinkler at position i waters everything from i − ranges[i] to i + ranges[i] - ●
Turn on any set of sprinklers. Every point from 0 to n must be watered; two watered stretches that merely touch at a point (for example [0, 3] and [3, 6]) still leave no gap - ●
Return the fewest sprinklers that water the whole path, or −1 if it is impossible
n =
ranges =