1326. Minimum Number of Taps to Open to Water a Garden
Description
There is a one-dimensional garden on the x-axis. The garden starts at the point 0
and ends at the point n
. (i.e., 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]
(0-indexed) means the i-th
tap can water the area [i - ranges[i], i + ranges[i]]
if it was 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: 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.
Constraints:
1 <= n <= 104
ranges.length == n + 1
0 <= ranges[i] <= 100
Solutions
Solution 1: Greedy
We note that for all taps that can cover a certain left endpoint, choosing the tap that can cover the farthest right endpoint is optimal.
Therefore, we can preprocess the array $ranges$. For the $i$-th tap, it can cover the left endpoint $l = \max(0, i - ranges[i])$ and the right endpoint $r = i + ranges[i]$. We calculate the position of the tap that can cover the left endpoint $l$ with the farthest right endpoint and record it in the array $last[i]$.
Then we define the following three variables:
- Variable $ans$ represents the final answer, i.e., the minimum number of taps;
- Variable $mx$ represents the farthest right endpoint that can currently be covered;
- Variable $pre$ represents the farthest right endpoint covered by the previous tap.
We traverse all positions in the range $[0, \ldots, n-1]$. For the current position $i$, we use $last[i]$ to update $mx$, i.e., $mx = \max(mx, last[i])$.
- If $mx \leq i$, it means the next position cannot be covered, so we return $-1$.
- If $pre = i$, it means a new subinterval needs to be used, so we increment $ans$ by $1$ and update $pre = mx$.
After the traversal, we return $ans$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the garden.
Similar problems:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|