> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/greedy_algorithm/minimum-number-of-taps-to-open-to-water-a-garden.md).

# Minimum Number of Taps to Open to Water a Garden

## Question ([LC.1326](https://leetcode.com/problems/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`. There are `n + 1` taps located at points `[0, 1, ..., n]` in the garden.
>
> Given the garden length `n` and a list of tap ranges `ranges` where `ranges[i]` can cover `[i - ranges[i], i + ranges[i]` when that tap is open, find the minimum number of taps open to water the whole garden. If the garden cannot be fully covered, return -1. 

## Example 

```
I: n = 5, ranges = [3,4,1,1,0,0]
O: 1 because the second tap can cover the entire garden [-3, 5]

I: n = 3, ranges = [0,0,0,0]
O: -1
```

## Approach 

This is one class of the interval scheduling problem. The goal is to find the minimum number of intervals to cover a target interval. 

![Taps ranges and garden (green) ](/files/LJ2Ngc8YvW3hrYhXluNf)

Assume an optimal solution $$O\_1 = \[R\_3, R\_2, R\_8, R\_5, R\_{11}, R\_6]$$

If $$R\_1$$ and $$R\_3$$ can resume from the same previous ending $$start\_{R\_1} \leq end\_{p}$$ and $$start\_{R\_3} \leq end\_p$$, and $$R\_1$$ runs longer than $$R\_3$$ $$end\_{R\_1} > end\_{R\_3}$$, then we can replace $$R\_3$$ with $$R\_1$$and the rest of solution can remain optimal. 

Therefore, by induction, the greedy choice of picking the longest interval with the same acceptable start time proves to be optimal. 

Sort by start time because we need to identify gaps $$start\_i > end\_p$$ between intervals to guarantee correctness. 

## Code 

```python
class Solution:
    def convert_rad_to_intv(self, index: int, radius: int) -> Tuple[int, int]:
        start = index - radius if index - radius > 0 else 0
        return start, index + radius

    def minTaps(self, n: int, ranges: List[int]) -> int:
        intvs = []
        for i in range(len(ranges)):
            if ranges[i] != 0:
                intvs.append(self.convert_rad_to_intv(i, ranges[i]))
        sorted_intvs = sorted(intvs, key=lambda elem: elem[0])

        prev_end = -1
        current_end = 0
        target_end = n
        count = 0

        for intv in sorted_intvs:
            if intv[0] > prev_end:
                # discontinuity
                if intv[0] > current_end:
                    return -1
                else:
                    # extend
                    if intv[1] > current_end:
                        count += 1
                        prev_end = current_end
                        current_end = intv[1]
            else:
                # swap
                if intv[1] > current_end:
                    current_end = intv[1]

            if current_end >= target_end:
                return count

        return -1
```

## Complexity 

Time O(nlogn) + O(n) Space O(n)