A gallery with plants is divided into n parts, numbered : 0,1,2,3...n-1. There are provisions for attaching water sprinklers at every partition. A sprinkler with range x at partition i can water all partitions from i-x to i+x.
Given an array gallery[ ] consisting of n integers, where gallery[i] is the range of sprinkler at partition i (power==-1 indicates no sprinkler attached), return the minimum number of sprinklers that need to be turned on to water the complete gallery.
If there is no possible way to water the full length using the given sprinklers, print -1.
Example 1:
Input:
n = 6
gallery[ ] = {-1, 2, 2, -1, 0, 0}
Output:
2
Explanation: Sprinklers at index 2 and 5
can water thefull gallery, span of
sprinkler at index 2 = [0,4] and span
of sprinkler at index 5 = [5,5].
Example 2:
Input:
n = 9
gallery[ ] = {2, 3, 4, -1, 2, 0, 0, -1, 0}
Output:
-1
Explanation: No sprinkler can throw water
at index 7. Hence all plants cannot be
watered.
Example 3:
Input:
n = 9
gallery[ ] = {2, 3, 4, -1, 0, 0, 0, 0, 0}
Output:
3
Explanation: Sprinkler at indexes 2, 7 and
8 together can water all plants.
Your task:
Your task is to complete the function min_sprinklers() which takes the array gallery[ ] and the integer n as input parameters and returns the value to be printed.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ n ≤ 10^{5}
gallery[i] ≤ 50

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def min_sprinklers(self, gallery, n):

        # code here





Solutions:
class Solution:

	def min_sprinklers(self, gallery, n):
		water = []
		for i in range(n):
			if gallery[i] != -1:
				water.append((i - gallery[i], i + gallery[i]))
		if len(water) == 0:
			return -1
		water.sort()
		ans = 0
		(left, right) = (0, 0)
		if water[0][0] > right:
			return -1
		else:
			ans = 1
			right = water[0][1]
		for i in range(1, len(water)):
			if right >= n - 1:
				break
			if water[i][0] <= left:
				right = max(right, water[i][1])
			elif water[i][0] > right + 1:
				return -1
			else:
				ans += 1
				left = right + 1
				right = water[i][1]
		return ans if right >= n - 1 else -1


class Solution:

	def min_sprinklers(self, gallery, n):
		l = []
		for i in range(n):
			if gallery[i] == -1:
				continue
			l.append([max(0, i - gallery[i]), min(n - 1, i + gallery[i])])
		l.sort()
		l1 = []
		for i in l:
			(a, b) = (i[0], i[1])
			flag = 0
			while len(l1) > 0 and l1[len(l1) - 1][0] >= a and (l1[len(l1) - 1][1] <= b):
				l1.pop()
				flag = 1
				continue
			if len(l1) > 0 and l1[len(l1) - 1][0] <= a and (l1[len(l1) - 1][1] >= b):
				continue
			if len(l1) > 0 and l1[len(l1) - 1][1] < b:
				if i[0] <= l1[len(l1) - 1][1]:
					l1.append([l1[len(l1) - 1][1] + 1, i[1]])
					continue
				l1.append(i)
			if len(l1) == 0:
				l1.append(i)
				continue
		g1 = dict()
		for i in range(n):
			g1[i] = True
		for i in l1:
			for j in range(i[0], i[1] + 1):
				g1[j] = False
		for i in g1.keys():
			if g1[i] == True:
				return -1
		if len(l1) == 0:
			return -1
		return len(l1)


class Solution:

	def min_sprinklers(self, gallery, n):
		sprinklers = []
		for i in range(n):
			if gallery[i] > -1:
				sprinklers.append([i - gallery[i], i + gallery[i]])
		sprinklers.sort()
		target = 0
		sprinklers_on = 0
		i = 0
		while target < n:
			if i == len(sprinklers) or sprinklers[i][0] > target:
				return -1
			max_range = sprinklers[i][1]
			while i + 1 < len(sprinklers) and sprinklers[i + 1][0] <= target:
				i += 1
				max_range = max(max_range, sprinklers[i][1])
			if max_range < target:
				return -1
			sprinklers_on += 1
			target = max_range + 1
			i += 1
		return sprinklers_on


class Solution:

	def min_sprinklers(self, gallery, n):
		target = 0
		count = 0
		di = []
		for i in range(n):
			if gallery[i] != -1:
				di.append([i - gallery[i], i + gallery[i]])
		di.sort(key=lambda x: x[0])
		m = len(di)
		idx = 0
		while target < n and idx < m:
			next_target = -1
			if di[idx][0] > target:
				return -1
			while idx < m and di[idx][0] <= target:
				next_target = max(next_target, di[idx][1])
				idx += 1
			target = next_target + 1
			count += 1
		return count if target >= n else -1


class Solution:

	def min_sprinklers(self, gallery, n):
		arr = []
		for i in range(n):
			if gallery[i] != -1:
				arr.append((i - gallery[i], i + gallery[i]))
		arr.sort(key=lambda x: x[0])
		left = 0
		i = 0
		c = 0
		while left < n:
			if i >= len(arr) or arr[i][0] > left:
				return -1
			curr = arr[i][1]
			while i + 1 < len(arr) and arr[i + 1][0] <= left:
				i += 1
				curr = max(curr, arr[i][1])
			if curr < left:
				return -1
			left = curr + 1
			c += 1
			i += 1
		return c