Leetcode 1451 Solution

This article provides solution to leetcode question 1451 (minimum-number-of-taps-to-open-to-water-a-garden)
Categories:
Tags:
Access this page by simply typing in "lcs 1451" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden

Solution

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        s = []
        for i, ran in enumerate(ranges):
            s.append((i - ran, i + ran))
        s.sort()

        q = []
        curr = 0
        i = 0
        ans = 0
        while curr < n:
            while i < len(s) and s[i][0] <= curr:
                heapq.heappush(q, -s[i][1])
                i += 1

            if not q:
                return -1

            curr = -heapq.heappop(q)
            ans += 1

        return ans