🚰Minimum Number of Taps to Open to Water a Garden

Question (LC.1326)

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)

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

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)