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


class Solution:

	def min_sprinklers(self, gallery, n):
		s = [[x - gallery[x], x + gallery[x]] for x in range(n) if gallery[x] != -1]
		s.sort()
		(target, res, i) = (0, 0, 0)
		while target < n:
			if i == len(s) or s[i][0] > target:
				return -1
			s_range = s[i][1]
			while i + 1 < len(s) and s[i + 1][0] <= target:
				i += 1
				s_range = max(s_range, s[i][1])
			if s_range < target:
				return -1
			res += 1
			target = s_range + 1
			i += 1
		return res


class Solution:

	def min_sprinklers(self, gallery, n):
		l = []
		for i in range(len(gallery)):
			if gallery[i] > -1:
				l.append([i - gallery[i], i + gallery[i]])
		l.sort(key=lambda x: x[0])
		target = 0
		i = 0
		ans = 0
		while target < n:
			if i == len(l) or l[i][0] > target:
				return -1
			maxrange = l[i][1]
			while i + 1 < len(l) and l[i + 1][0] <= target:
				i += 1
				maxrange = max(maxrange, l[i][1])
			ans += 1
			target = maxrange + 1
			i += 1
		return ans


class Solution:

	def min_sprinklers(self, gallery, n):
		V = []
		N = n
		arr = gallery
		for i in range(N):
			if arr[i] > -1:
				V.append([i - arr[i], i + arr[i]])
		V.sort()
		maxRight = 0
		res = 0
		i = 0
		while maxRight < N:
			if i == len(V) or V[i][0] > maxRight:
				return -1
			currMax = V[i][1]
			while i + 1 < len(V) and V[i + 1][0] <= maxRight:
				i += 1
				currMax = max(currMax, V[i][1])
			if currMax < maxRight:
				return -1
			res += 1
			maxRight = currMax + 1
			i += 1
		return res


class Solution:

	def min_sprinklers(self, gallery, n):
		l = []
		for i in range(n):
			if gallery[i] != -1:
				l.append([max(0, i - gallery[i]), min(n - 1, i + gallery[i])])
		l.sort(key=lambda x: (x[0], -x[1]))
		stack = []
		curr_right = 0
		for i in range(len(l)):
			if l[i][0] > curr_right:
				return -1
			if not stack:
				stack.append(l[i])
			elif stack[-1][1] >= l[i][1]:
				continue
			elif stack[-1][0] >= l[i][0]:
				(lef, right) = stack.pop()
				stack.append([lef, l[i][1]])
			else:
				(lef, rig) = stack[-1]
				stack.append([rig + 1, l[i][1]])
			curr_right = stack[-1][1] + 1
		return len(stack) if curr_right == n else -1


class Solution:

	def min_sprinklers(self, A, N):
		sp = []
		for i in range(N):
			if A[i] != -1:
				sp.append([i - A[i], i + A[i]])
		sp.sort()
		target = 0
		spcount = 0
		i = 0
		if len(sp) == 0:
			return -1
		while target < N:
			if i == len(sp) or sp[i][0] > target:
				return -1
			nxt = sp[i][1]
			j = i + 1
			while j < len(sp) and sp[j][0] <= target:
				nxt = max(nxt, sp[j][1])
				j += 1
			if nxt < target:
				return -1
			spcount += 1
			i = j
			target = nxt + 1
		return spcount


class Solution:

	def min_sprinklers(self, gallery, n):
		rang = []
		for i in range(n):
			if gallery[i] != -1:
				rang.append([i - gallery[i], i + gallery[i]])
		rang.sort()
		r = len(rang)
		covered = 0
		res = 0
		i = 0
		while covered < n:
			if i == r or rang[i][0] > covered:
				return -1
			currcov = rang[i][1]
			while i + 1 < r and rang[i + 1][0] <= covered:
				currcov = max(currcov, rang[i + 1][1])
				i += 1
			res += 1
			covered = currcov + 1
			i += 1
		return res


class Solution:

	def min_sprinklers(self, gallery, n):
		arr = []
		for (i, val) in enumerate(gallery):
			if val == -1:
				continue
			x = i - val
			y = i + val
			if x < 0:
				x = 0
			if y >= n:
				y = n - 1
			arr.append([x, y])
		if len(arr) == 0:
			return -1
		arr.sort()
		(start, i, ans) = (0, 0, 0)
		while start < n:
			maxReach = -1000000000.0
			while i < len(arr):
				if arr[i][0] > start:
					break
				maxReach = max(maxReach, arr[i][1])
				i += 1
			if maxReach < start:
				return -1
			ans += 1
			start = maxReach + 1
		return ans


class Solution:

	def min_sprinklers(self, gallery, n):
		v = [-1] * n
		for i in range(n):
			if gallery[i] == -1:
				continue
			elif v[i] < i + gallery[i]:
				l = i - gallery[i]
				r = i + gallery[i]
				for j in range(l, r + 1):
					if j < 0 or j >= n:
						continue
					else:
						v[j] = r
		c = 0
		i = 0
		while i < n:
			if v[i] == -1:
				return -1
			i = v[i]
			c += 1
			i += 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		gallery = [int(x) for x in input().strip().split()]
		obj = Solution()
		print(obj.min_sprinklers(gallery, n))


class Solution:

	def min_sprinklers(self, gallery, n):
		v = []
		for (index, value) in enumerate(gallery):
			v.append([index - value, index + value])
		v.sort()
		res = 0
		maxRight = 0
		i = 0
		while maxRight < n:
			if i == len(v) or v[i][0] > maxRight:
				return -1
			curMax = v[i][1]
			while i + 1 < len(v) and v[i + 1][0] <= maxRight:
				i += 1
				curMax = max(curMax, v[i][1])
			if curMax < maxRight:
				return -1
			maxRight = curMax + 1
			res += 1
			i += 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		gallery = [int(x) for x in input().strip().split()]
		obj = Solution()
		print(obj.min_sprinklers(gallery, n))


class Solution:

	def min_sprinklers(self, gallery, n):
		res = 0
		maxreach = -1
		v = []
		for i in range(n):
			if gallery[i] > -1:
				v.append((i - gallery[i], i + gallery[i]))
		v.sort()
		i = 0
		while maxreach <= n - 2:
			if i == len(v) or v[i][0] >= maxreach + 2:
				return -1
			curreach = v[i][1]
			while i + 1 < len(v) and v[i + 1][0] <= maxreach + 1:
				i += 1
				curreach = max(curreach, v[i][1])
			if curreach < maxreach:
				return -1
			maxreach = curreach
			i += 1
			res += 1
		if res == 0 and n != 0:
			return -1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		gallery = [int(x) for x in input().strip().split()]
		obj = Solution()
		print(obj.min_sprinklers(gallery, n))


class Solution:

	def min_sprinklers(self, gallery, n):
		lines = []
		for i in range(n):
			if gallery[i] != -1:
				lines.append([max(i - gallery[i], 0), min(i + gallery[i], n - 1)])
		if len(lines) == 0:
			return -1
		lines.sort()
		if lines[0][0] != 0:
			return -1
		(start, ladder, jumps) = (0, 0, 0)
		j = 0
		while start < n:
			while j < len(lines) and lines[j][0] <= start:
				ladder = max(ladder, lines[j][1])
				j += 1
			if ladder + 1 == start:
				return -1
			jumps += 1
			start = ladder + 1
		return jumps
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		gallery = [int(x) for x in input().strip().split()]
		obj = Solution()
		print(obj.min_sprinklers(gallery, n))


class Solution:

	def min_sprinklers(self, gallery, n):
		arr = []
		for i in range(n):
			if gallery[i] != -1:
				arr.append([max(0, i - gallery[i]), min(n - 1, i + gallery[i])])
		arr.sort()
		start = 0
		i = 0
		ans = 0
		while start < n:
			maxi = -1000000000.0
			while i < len(arr):
				if arr[i][0] > start:
					break
				maxi = max(maxi, arr[i][1])
				i += 1
			if maxi < start:
				return -1
			start = maxi + 1
			ans += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		gallery = [int(x) for x in input().strip().split()]
		obj = Solution()
		print(obj.min_sprinklers(gallery, n))


class Solution:

	def min_sprinklers(self, gallery, n):
		arr = []
		for i in range(n):
			if gallery[i] != -1:
				arr.append([max(0, i - gallery[i]), min(n - 1, i + gallery[i])])
		arr.sort()
		start = 0
		i = 0
		ans = 0
		while start < n:
			maxi = -1000000000.0
			while i < len(arr):
				if arr[i][0] > start:
					break
				maxi = max(maxi, arr[i][1])
				i += 1
			if maxi < start:
				return -1
			start = maxi + 1
			ans += 1
		return ans


class Solution:

	def min_sprinklers(self, g, n):
		pref = [0 for i in range(0, n + 3)]
		cnt = 0
		l = []
		for i in range(0, n):
			if g[i] == -1:
				continue
			l.append([i - g[i], i + g[i]])
		l.sort()
		if len(l) == 0:
			return -1
		(i, target, res) = (0, 0, 0)
		while target < n:
			if i == len(l) or target < l[i][0]:
				return -1
			mx_range = l[i][1]
			while i + 1 < len(l) and l[i + 1][0] <= target:
				i += 1
				mx_range = max(mx_range, l[i][1])
			i = i + 1
			target = mx_range + 1
			res = res + 1
		return res


class Solution:

	def min_sprinklers(self, gallery, n):
		span = []
		for i in range(n):
			if gallery[i] == -1:
				continue
			low = i - gallery[i]
			high = i + gallery[i]
			if low < 0:
				low = 0
			if high >= n:
				high = n - 1
			span.append([low, high])
		span.sort(key=lambda x: x[0])
		ans = 0
		i = 0
		maxRight = 0
		while maxRight < n:
			currMax = -1000000000
			while i < len(span):
				if span[i][0] > maxRight:
					break
				currMax = max(currMax, span[i][1])
				i += 1
			if currMax < maxRight:
				return -1
			ans += 1
			maxRight = currMax + 1
		return ans


class Solution:

	def min_sprinklers(self, gallery, n):
		intervals = []
		for i in range(n):
			x = gallery[i]
			if x >= 0:
				(lb, ub) = (max(0, i - x), min(i + x, n - 1))
				intervals.append([lb, ub])
		if not intervals:
			return -1
		intervals.sort(key=lambda x: [x[0], -x[1]])
		if intervals[0][0] > 0:
			return -1
		chosen = [intervals[0]]

		def helper(i):
			lb = chosen[-1][1]
			if intervals[i][0] > lb + 1:
				return -1
			(ans, ub) = (i, intervals[i][1])
			for j in range(i + 1, len(intervals)):
				(a, b) = intervals[j]
				if a > lb + 1:
					break
				if b > ub:
					(ans, ub) = (j, b)
			if ub < lb + 1:
				return -1
			return ans
		i = 1
		while i < len(intervals) and chosen[-1][1] < n - 1:
			j = helper(i)
			if j == -1:
				return -1
			chosen.append(intervals[j])
			i = j + 1
		if chosen[-1][1] < n - 1:
			return -1
		else:
			return len(chosen)


class Solution:

	def min_sprinklers(self, g, n):
		a = []
		for i in range(n):
			if g[i] != -1:
				a.append([i - g[i], i + g[i]])
		a.sort()
		mx = 0
		res = 0
		i = 0
		while mx < n:
			if i == len(a) or a[i][0] > mx:
				return -1
			c = a[i][1]
			while i + 1 < len(a) and a[i + 1][0] <= mx:
				i += 1
				c = max(c, a[i][1])
			if c < mx:
				return -1
			res += 1
			mx = c + 1
			i += 1
		return res


class Solution:

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


class point:

	def __init__(self, x, i):
		self.ini = i - x
		self.final = i + x
		self.diff = self.final - self.ini
		self.data = x

class Solution:

	def min_sprinklers(self, gallery, n):
		lt = []
		c = 0
		for i in range(n):
			if gallery[i] != -1:
				lt.append(point(gallery[i], i))
				c += 1
		lt = sorted(lt, key=lambda x: x.ini)
		target = 0
		ans = 0
		curr_max = 0
		i = 0
		while target < n:
			if i == c or lt[i].ini > target:
				return -1
			curr_max = lt[i].final
			while i + 1 < c and lt[i + 1].ini <= target:
				i += 1
				curr_max = max(curr_max, lt[i].final)
			if curr_max < target:
				return -1
			target = curr_max + 1
			ans += 1
			i += 1
		return ans


from queue import PriorityQueue

class Solution:

	def min_sprinklers(self, gallery, n):
		clips = []
		if n == 1 and gallery[0] == -1:
			return -1
		for i in range(n):
			if gallery[i] != -1:
				a = i - gallery[i] if i - gallery[i] >= 0 else 0
				b = i + gallery[i] if i + gallery[i] < n else n - 1
				clips.append([a, b])
		if len(clips) == 0:
			return -1
		clips.sort(key=lambda x: (x[0], -x[1]))
		count = 1
		if clips[0][0] != 0:
			return -1
		max_e = clips[0][1]
		i = 1
		while i < len(clips):
			if max_e >= n - 1:
				return count
			temp = max_e
			new_max_e = -1
			while i < len(clips) and clips[i][0] <= temp + 1:
				if clips[i][1] > new_max_e:
					new_max_e = clips[i][1]
				i += 1
			if new_max_e > max_e:
				max_e = new_max_e
				count += 1
			else:
				return -1
		if max_e >= n - 1:
			return count
		return -1


import heapq

class Solution:

	def min_sprinklers(self, gallery, n):
		available = []
		not_available = []
		for i in range(n):
			if gallery[i] != -1:
				sprinkler = (max(0, i - gallery[i]), min(n - 1, i + gallery[i]))
				heapq.heappush(not_available, sprinkler)
		curr_max = -1
		count = 0
		while not_available or available:
			while not_available and not_available[0][0] <= curr_max + 1:
				sprinkler = heapq.heappop(not_available)
				heapq.heappush(available, (-sprinkler[1], sprinkler[0]))
			if not available:
				return -1
			sprinkler = heapq.heappop(available)
			if curr_max >= -sprinkler[0]:
				return -1
			else:
				curr_max = -sprinkler[0]
				count += 1
			if curr_max == n - 1:
				return count
		return -1