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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 104
	ranges.length == n + 1
	0 &lt;= ranges[i] &lt;= 100


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        maxRanges = [0]
        for i in range(len(ranges)):
            minIdx = max(i - ranges[i], 0)
            maxIdx = min(i + ranges[i], n)
            idx = bisect_left(maxRanges, minIdx)
            if idx == len(maxRanges) or maxIdx <= maxRanges[idx]: continue
            if idx == len(maxRanges) - 1:
                maxRanges.append(maxIdx)
            else:
                maxRanges[idx + 1] = max(maxRanges[idx + 1], maxIdx)
        if maxRanges[-1] < n:
            return -1
        else:
            return len(maxRanges) - 1
class Solution {
    public int minTaps(int n, int[] ranges) {
        Integer[] idx = IntStream.range(0, ranges.length).boxed().toArray(Integer[]::new);
        Arrays.sort(idx, Comparator.comparingInt(o -> o-ranges[o]));
        int ans = 1, cur = 0, end = 0;
        for (int i = 0;i<ranges.length&&end<n;i++){
            int j = idx[i];
            if (j-ranges[j]>cur){
                cur=end;
                ans++;
            }
            if (j-ranges[j]<=cur){
                end=Math.max(end, j+ranges[j]);
            }
        }
        return end<n?-1:ans;
    }
}
class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<pair<int,int>> v;
        for(int i=0;i<ranges.size();i++){
            // making ranges
            v.push_back({i-ranges[i],i+ranges[i]});
        }
        // sorting the intervals
        sort(v.begin(),v.end());
        
        // to keep track from where we need to cover
        int uncovered = 0;
        int idx = 0;
        // number of ranges used
        int cnt = 0;
        
        // to check if its possible
        bool ok = true;
        
        // as long as we have not covered the garden
        while(uncovered<n){
            // we will try to cover the uncovered such that new uncovered is maximum possible
            int new_uncovered = uncovered;
            while(idx<n+1 && v[idx].first<=uncovered){
                new_uncovered = max(new_uncovered,v[idx].second);
                idx++;
            }
            // we have used one range
            cnt++;
            
            // it means we were not able to cover with ranges so not possible
            if(new_uncovered == uncovered){
                ok = false;
                break;
            }
            // updating uncovered for next iteration
            uncovered = new_uncovered;
        }
        if(ok) return cnt;
        return -1;
    }
};
var minTaps = function(n, ranges) {
    let intervals = [];
    for (let i = 0; i < ranges.length; i++) {
        let l = i - ranges[i];
        let r = i + ranges[i];
        intervals.push([l, r]);
    }

    intervals.sort((a, b) => {
        if (a[0] === b[0]) return b[1] - a[1];
        return a[0] - b[0];
    })

    // Find the starting idx
    let startIdx;
    for (let i = 0; i < intervals.length; i++) {
        let [s, e] = intervals[i];
        if (s <= 0) {
            if (startIdx === undefined) startIdx = i;
            else if (intervals[startIdx][1] < e) startIdx = i;
        } else break;
    }
    if (startIdx === undefined) return -1;

    let q = [startIdx], openedTaps = 1;
    while (q.length) {
        let max;
        while (q.length) {
            let idx = q.pop();
            let [start, end] = intervals[idx];
            if (end >= n) return openedTaps;
            for (let i = idx + 1; i < intervals.length; i++) {
                let [nextStart, nextEnd] = intervals[i];
                // If next interval's start is less than the current interval's end
                if (nextStart <= end) {
                    if (!max && nextEnd > end) max = {i, end: nextEnd};
                    // If the next interval's end is greater than the current interval's end
                    else if (max && nextEnd > max.end) max = {i, end: nextEnd};
                }
                else break;
            }
        }
        if (max) {
            q.push(max.i);
            openedTaps++;
        }
    }

    return -1;
};
Minimum Number of Taps to Open to Water a Garden