#1326
Minimum Number of Taps to Open to Water a Garden
candidate master · 1400 · lc hard +32 · verified · 51% accepted · 3,617 likes · top 40%
Description
A one-dimensional garden spans from position 0 to position n along the x-axis. There are n + 1 taps at positions 0, 1, ..., n. Opening tap i waters the interval [i - ranges[i], i + ranges[i]], as defined by the given array ranges. Return the minimum number of taps to open so that the entire garden [0, n] is watered, or -1 if full coverage is impossible.
Example 1:
Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]
Example 2:
Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.
Code
1
2
3