Minimum Number of Taps to Open to Water a Garden

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.
Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3
Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2
Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1
 

Constraints:


Solution:

class Solution {
    public int minTaps(int n, int[] ranges) {
        int[][] taps = new int[n + 1][2];
        for (int i = 0; i < n + 1; i ++) {
            taps[i] = new int[]{Math.max(0, i - ranges[i]), i + ranges[i]};
        }
        Arrays.sort(taps, (a, b) -> Integer.compare(a[0], b[0]) == 0 ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0]));
        // for (int i = 0; i < n + 1; i ++) {
        //     System.out.print(Arrays.toString(taps[i]) + ", ");
        // }
        int end = 0, count = 1;
        if (taps[end][0] > 0) return -1;
        while (end < n + 1) {
            int[] last = taps[end];
            if (last[1] >= n) return count;
            int prevEnd = end;
            for (int j = end + 1; j < n + 1; j ++) {
                int[] curr = taps[j];
                if (curr[1] <= last[1]) continue;
                if (curr[0] > last[1]) break;
                if (curr[1] > taps[end][1]) {
                    end = j;
                }
            }
            if (end != prevEnd) {
                count ++;
            } else {
                break;
            }
        }
        if (taps[end][1] >= n) return count;
        return -1;
    }
}