# 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) 


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/greedy_algorithm/minimum-number-of-taps-to-open-to-water-a-garden.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.