• 欢迎光临~

# [Oracle] LeetCode 1326 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`.

### Solution

``````class Solution {
private:
int ans=0;
vector<vector<int>> itv;
public:
int minTaps(int n, vector<int>& ranges) {
for(int i=0;i<n+1;i++){
itv.push_back({i-ranges[i], i+ranges[i]});
}
sort(itv.begin(), itv.end());
int st=0, ed=0;
int i=0;
while(st<n){
while(i<itv.size() && itv[i]<=st){
ed = max(ed, itv[i]); i++;
}
if(st==ed)return -1;
st = ed;
ans++;
}
return ans;
}
};
``````