# 1326. Minimum Number of Taps to Open to Water a Garden
###### tags: `Leetcode` `Medium` `Greedy` `Intervals`
Link: https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/description/
## 思路
和[1024. Video Stitching](https://hackmd.io/DLEdtqZQTC-_GZZbrfkRrg)很像
注意无解的情况有三种：
1. 最右端的位置还没有推进到n，但是区间i之后已经没有任何其他区间能与之重叠
2. 如果考察完所有的区间，最右端的位置仍然无法推进到n
3. 第一个区间的左端点在0后面
## Code

class Solution {
    public int minTaps(int n, int[] ranges) {
        List<int[]> list = new ArrayList<>();
        for(int i=0; i<ranges.length; i++){
            list.add(new int[]{i-ranges[i], i+ranges[i]});
        }
        Collections.sort(list, (a,b)->(a[0]-b[0]));
        if(list.get(0)[0]>0) return -1;
        int far = 0;
        int nextfar = 0;
        int ans = 1;
        for(int i=0; i<list.size(); i++){
            if(list.get(i)[0]>far){
                if(far>=nextfar) return -1;
                far = nextfar;
                ans++;
            }
            nextfar = Math.max(nextfar, list.get(i)[1]);
            if(nextfar>=n) return ans;
        }
        return -1;
    }
}