1326. Minimum Number of Taps to Open to Water a Garden Hard

1/**
2 * [1326] Minimum Number of Taps to Open to Water a Garden
3 *
4 * 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).
5 * There are n + 1 taps located at points [0, 1, ..., n] in the garden.
6 * 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.
7 * Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2020/01/16/1685_example_1.png" style="width: 525px; height: 255px;" />
11 * Input: n = 5, ranges = [3,4,1,1,0,0]
12 * Output: 1
13 * Explanation: The tap at point 0 can cover the interval [-3,3]
14 * The tap at point 1 can cover the interval [-3,5]
15 * The tap at point 2 can cover the interval [1,3]
16 * The tap at point 3 can cover the interval [2,4]
17 * The tap at point 4 can cover the interval [4,4]
18 * The tap at point 5 can cover the interval [5,5]
19 * Opening Only the second tap will water the whole garden [0,5]
20 * 
21 * Example 2:
22 * 
23 * Input: n = 3, ranges = [0,0,0,0]
24 * Output: -1
25 * Explanation: Even if you activate all the four taps you cannot water the whole garden.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	1 <= n <= 10^4
31 * 	ranges.length == n + 1
32 * 	0 <= ranges[i] <= 100
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/
38// discuss: https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn min_taps(n: i32, ranges: Vec<i32>) -> i32 {
44        0
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_1326() {
56    }
57}
58