Minimum Number of Taps to Open to Water a Garden
There is a one-dimensional garden on the x-axis. The garden starts at point 0 and ends at point n; that is, the length of the garden is n.
There are n + 1 taps located at points [0, 1, ..., n] in the garden.
Given an integer n and an integer array ranges of length n + 1, where ranges[i] means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it is open, return the minimum number of taps that should be open to water the whole garden.
If the garden cannot be watered, return -1.
Example 1
Input
n = 5, ranges = [3,4,1,1,0,0]Output
1Opening only the tap at point 1 covers the entire garden interval [0, 5].
Example 2
Input
n = 3, ranges = [0,0,0,0]Output
-1Even if all four taps are activated, the whole garden cannot be watered.
Constraints
- 1 <= n <= 10^4
- ranges.length == n + 1
- 0 <= ranges[i] <= 100