Problem statement

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

Solution

Actually, this problem asks: what is minimum number of intervals needed to cover range [0, n]. We can use the greedy strategy: imagine, that we already covered interval [0, r]. Then we sort all intervals by their left points and then we look at all intervals which intersect with [0, r], that is which left point is less or equal than $r$ and look for interval with maximum right point. i is pointer for current interval. When we checked all intervals which intersect with [0, r], we check if we reached the end or we stuck: r2 = r and if we are, return -1. If not, increase ans by one and put r2 equal to r.

Complexity

Time complexity is $O(n\log n)$, space complexity is $O(n)$.

Code

class Solution:
    def minTaps(self, n, R):
        ints = sorted([(max(0, i-R[i]), min(i+R[i], n)) for i in range(n+1)])
        
        ans, r, i = 0, 0, 0

        while i < n + 1 and r < n:
            r2 = r
            while i < n + 1 and ints[i][0] <= r:
                r2 = max(r2, ints[i][1])
                i += 1
                
            if r2 == r != n: return -1        
            ans, r = ans + 1, r2 
            
        return ans

Remark

Actually this problem is exactly as 1024, but with bigger constraints. It is in fact similar to problem 0045 Jump game II there is $O(n*Q)$ solution, where $Q$ is maximum size of range, which will pass as well.