## Problem

**Problem ID**: 1326

**Title**: Minimum Number of Taps to Open to Water a Garden

**Difficulty**: Hard

**Description**:

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.

## Thoughts

This is quite a tricky problem as it does not use the definition of an interval. Intervals `(i, j)`

and `(j+1, k)`

do not cover the entire range
from `i`

to `k`

.

The key to solving this question is to identify that it is a greedy problem. A model I like to use is to ask myself,
at point `i`

, if I choose the interval that contains `i`

and ends the latest, will the answer be wrong when I process
the intervals beyond `i`

?

## Implementation

`O(nlog(n))`

solution

**General Idea**: Similar to LC 56: merge interval questions, we would
sort the ranges from by the start of intervals.

**Handling edge case**: for `ranges=0`

we would artificially set the range to `(-1,-1)`

as it would not contribute
to the intervals.

```
class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<pair<int,int>> intervals(ranges.size());
for (int i = 0; i < ranges.size(); i++) {
if (ranges[i] == 0) {
// tap will not be able cover its own location so shift it to -1
intervals[i] = make_pair(-1, -1);
} else {
intervals[i] = make_pair(i-ranges[i], i+ranges[i]);
}
}
sort(intervals.begin(), intervals.end());
int next_uncovered;
int count = 0;
int curr_interval = 0;
int last_covered = -1;
for (int i = 0; i < intervals.size(); i++) {
if (i < last_covered) continue;
if (i == intervals.size() -1 && i <= last_covered) break;
while (curr_interval < intervals.size()) {
int start = intervals[curr_interval].first;
int end = intervals[curr_interval].second;
if (start > i) break;
last_covered = max(last_covered, end);
curr_interval++;
}
if (last_covered < i) return -1;
count++;
}
return count;
}
};
```