There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).
There are n + 1 taps located at points [0, 1, ..., n] in the garden.
Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
 
Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:
Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Example 3:
Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3

Example 4:
Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2

Example 5:
Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1

 
Constraints:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        

Solutions:
class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		for (i, r) in enumerate(ranges):
			l = max(0, i - r)
			ranges[l] = max(i + r, ranges[l])
		res = lo = hi = 0
		while hi < n:
			(lo, hi) = (hi, max(ranges[lo:hi + 1]))
			if hi == lo:
				return -1
			res += 1
		return res


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		if not ranges:
			return 0
		N = len(ranges)
		max_right_end = list(range(N))
		for (i, a) in enumerate(ranges):
			max_right_end[max(i - a, 0)] = min(i + a, N - 1)
		print(max_right_end)
		(res, l, r) = (0, 0, max_right_end[0])
		while True:
			res += 1
			if r >= N - 1:
				return res
			new_r = max(max_right_end[l:r + 1])
			if new_r == r:
				return -1
			(l, r) = (r, new_r)


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:

		def parse_ranges(ranges):
			intervals = []
			for (idx, distance) in enumerate(ranges):
				left = max(0, idx - distance)
				right = min(n, idx + distance)
				intervals.append([left, right])
			return intervals
		watered = []
		intervals = parse_ranges(ranges)
		intervals.sort(key=lambda time: (time[0], -time[1]))
		for (start, end) in intervals:
			if watered and watered[-1][1] >= end:
				continue
			if watered and start - watered[-1][1] > 0:
				return -1
			if len(watered) >= 2 and start <= watered[-2][1]:
				watered[-1] = [start, end]
			else:
				watered.append([start, end])
		return len(watered) if watered[-1][-1] >= n else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [0] + [n + 2] * n
		for (i, x) in enumerate(ranges):
			for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
				dp[j] = min(dp[j], dp[max(i - x, 0)] + 1)
		return dp[n] if dp[n] < n + 2 else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [0] + [n + 2] * n
		for (i, v) in enumerate(ranges):
			left = max(i - v, 0)
			right = min(i + v, n)
			for j in range(left + 1, right + 1):
				dp[j] = min(dp[j], dp[max(0, i - v)] + 1)
		if dp[n] < n + 2:
			return dp[n]
		return -1


class Solution:

	def minTaps(self, n, A):
		dp = [0] + [n + 2] * n
		for (i, x) in enumerate(A):
			for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
				dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
		return dp[n] if dp[n] < n + 2 else -1


class Solution:

	def minTaps(self, n: int, ranges) -> int:
		dp = [0] + [float('inf')] * n
		for (i, x) in enumerate(ranges):
			for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
				dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
		print(dp)
		return dp[n] if dp[n] != float('inf') else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		(min_range, max_range, open_taps) = (0, 0, 0)
		while max_range < n:
			for (i, r) in enumerate(ranges):
				if i - r <= min_range and i + r >= max_range:
					max_range = i + r
			if min_range == max_range:
				return -1
			open_taps += 1
			min_range = max_range
		return open_taps


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		lowest_missing = 0
		taps = 0
		while lowest_missing < n:
			highest = None
			for (idx, tap) in enumerate(ranges):
				if idx - tap > lowest_missing or idx + tap < lowest_missing + 1:
					continue
				if highest is None or highest < idx + tap:
					highest = idx + tap
			if highest is None:
				return -1
			lowest_missing = highest
			taps += 1
		return taps


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [sys.maxsize] * (n + 1)
		dp[0] = 0
		for i in range(n + 1):
			for j in range(max(0, i - ranges[i]), min(n, i + ranges[i]) + 1):
				dp[j] = min(dp[j], 1 + dp[max(0, i - ranges[i])])
		if dp[n] == sys.maxsize:
			return -1
		return dp[n]


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		res = 0
		DP = [float('inf')] * (n + 1)
		farest = 0
		DP[0] = 0
		for (i, r) in enumerate(ranges):
			for x in range(max(i - r, 0), min(i + r + 1, n + 1)):
				DP[x] = min(DP[x], DP[max(i - r, 0)] + 1)
		return DP[-1] if DP[-1] != float('inf') else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for (idx, r) in enumerate(ranges):
			for j in range(max(idx - r + 1, 0), min(idx + r, n) + 1):
				dp[j] = min(dp[j], dp[max(0, idx - r)] + 1)
		return dp[n] if dp[n] < float('inf') else -1


class Solution:

	def minTaps1(self, n: int, ranges: List[int]) -> int:
		intervals = []
		for i in range(n + 1):
			if ranges[i]:
				left = max(0, i - ranges[i])
				right = min(n, i + ranges[i])
				intervals.append((left, right))
		intervals.sort()
		res = 0
		max_pos = 0
		prev_max_pos = -1
		for (i, j) in intervals:
			if max_pos >= n:
				break
			if i > max_pos:
				return -1
			elif prev_max_pos < i <= max_pos:
				res = res + 1
				prev_max_pos = max_pos
				print((i, j), res)
			max_pos = max(max_pos, j)
		return res if max_pos >= n else -1

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [0] + [n + 1] * n
		for (i, x) in enumerate(ranges):
			for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
				dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
		return dp[n] if dp[n] < n + 1 else -1


from heapq import heappush, heappop

class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		taps_by_start = []
		for (i, r) in enumerate(ranges):
			if r != 0:
				tap = (max(0, i - r), i + r)
				heappush(taps_by_start, tap)
		taps_by_end = []
		current_min = 0
		num_of_pipe = 0
		while current_min < n:
			while taps_by_start and taps_by_start[0][0] <= current_min:
				tap = heappop(taps_by_start)
				tap_reverse = (-tap[1], tap[0])
				heappush(taps_by_end, tap_reverse)
			if taps_by_end:
				next_pipe = heappop(taps_by_end)
				current_min = -next_pipe[0]
				num_of_pipe += 1
			else:
				return -1
		return num_of_pipe


from math import inf

class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [inf] * (n + 1)
		for i in range(n + 1):
			if not ranges[i]:
				continue
			s = i - ranges[i]
			if s <= 0:
				dp[i] = 1
			else:
				dp[i] = 1 + min([dp[j] for j in range(max(0, s - 100), i) if ranges[j] and j + ranges[j] >= s] + [inf])
		res = min([dp[i] for i in range(n + 1) if ranges[i] and i + ranges[i] >= n] + [inf])
		return res if res != inf else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		(min_range, max_range, open_taps, idx) = (0, 0, 0, 0)
		while max_range < n:
			for i in range(len(ranges)):
				if i - ranges[i] <= min_range and i + ranges[i] >= max_range:
					max_range = i + ranges[i]
			if min_range == max_range:
				return -1
			open_taps += 1
			min_range = max_range
		return open_taps


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		farthestRightAt = [-1] * (n + 1)
		for (i, r) in enumerate(ranges):
			if r == 0:
				continue
			left = i - r
			right = i + r
			for j in range(max(0, left), min(right + 1, n + 1)):
				farthestRightAt[j] = min(n, max(farthestRightAt[j], right))
		if -1 in farthestRightAt:
			return -1
		i = 0
		count = 0
		while i < n:
			i = farthestRightAt[i]
			count += 1
		return count


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		sorted_ranges = [(max(0, i - v), min(n, i + v)) for (i, v) in enumerate(ranges)]
		dicts = {}
		for i in sorted_ranges:
			dicts[i[0]] = max(i[1], dicts.get(i[0], -10000000000.0))
		reduced_ranges = sorted([(k, v) for (k, v) in dicts.items()])
		prev_max = max_e = reduced_ranges[0][1]
		min_start = reduced_ranges[0][0]
		taps = 1
		i = 0
		(s, e) = reduced_ranges[i]
		print(reduced_ranges)
		while max_e < n:
			taps += 1
			while True:
				(s, e) = reduced_ranges[i + 1]
				if s > prev_max:
					break
				max_e = max(e, max_e)
				i += 1
				if max_e >= n:
					return taps
			if max_e == prev_max:
				return -1
			prev_max = max_e
			max_e = max_e
		return taps


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		taps = []
		for i in range(len(ranges)):
			taps.append((i - ranges[i], i + ranges[i]))
		taps.sort()

		@lru_cache(None)
		def helper(i):
			if i >= n + 1:
				return float('inf')
			if taps[i][1] >= n:
				return 1
			ans = float('inf')
			for j in range(i + 1, n + 1):
				if taps[j][0] > taps[i][1]:
					break
				if taps[j][0] <= taps[i][1] and taps[j][1] > taps[i][1]:
					ans = min(ans, 1 + helper(j))
			return ans
		ans = float('inf')
		for i in range(n, -1, -1):
			res = helper(i)
			if taps[i][0] <= 0 and res < ans:
				ans = res
		return -1 if ans == float('inf') else ans


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		stack = []
		for i in range(n + 1):
			(l, r) = (i - ranges[i], i + ranges[i])
			if not stack or (l <= 0 and r >= stack[-1]):
				stack = [r]
			elif l <= stack[-1] < r:
				while len(stack) > 1:
					prev = stack.pop()
					if l > stack[-1]:
						stack.append(prev)
						break
				stack.append(r)
			if stack[-1] >= n:
				return len(stack)
		return -1

class Solution:

	def minTaps(self, n, A):
		dp = [0] + [n + 2] * n
		for (i, x) in enumerate(A):
			for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
				dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
		return dp[n] if dp[n] < n + 2 else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		minimum = 0
		maximum = 0
		total = 0
		while maximum < n:
			for i in range(len(ranges)):
				left = i - ranges[i]
				right = i + ranges[i]
				if left <= minimum and right > maximum:
					maximum = right
			if minimum == maximum:
				return -1
			minimum = maximum
			total += 1
		return total


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		ranges = [[i - val, i + val] for (i, val) in enumerate(ranges)]
		ranges.sort()
		print(ranges)
		max_reach = 0
		i = 0
		taps = 0
		while max_reach < n:
			curr_reach = 0
			if max_reach == 6:
				print(3)
			while i < n + 1 and ranges[i][0] <= max_reach:
				curr_reach = max(curr_reach, ranges[i][1])
				i += 1
			print(curr_reach, max_reach)
			if curr_reach <= max_reach:
				return -1
			max_reach = curr_reach
			taps += 1
		return taps


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		windows = []
		for (i, range) in enumerate(ranges):
			windows.append((max(0, i - range), i + range))
		windows.sort()
		i = 0
		max_water = 0
		num_taps = 0
		while i < len(windows):
			if max_water >= n:
				return num_taps
			num_taps += 1
			prev_water = max_water
			j = i
			while j < len(windows) and windows[j][0] <= prev_water:
				if windows[j][1] > max_water:
					max_water = windows[j][1]
				j += 1
			if max_water == prev_water:
				break
			i = j
		return -1 if max_water < n else num_taps


def redundant(a, b):
	((al, ar), (bl, br)) = (a, b)
	return al <= bl <= br <= ar or bl <= al <= ar <= br

def union(a, b):
	((al, ar), (bl, br)) = (a, b)
	return (min(al, bl), max(ar, br))

def remove_overlap(ranges):
	ans = []
	for rng in ranges:
		ans.append(rng)
		while len(ans) >= 2 and redundant(ans[-2], ans[-1]):
			b = ans.pop()
			a = ans.pop()
			ans.append(union(a, b))
	return ans

def union_covers(a, b, c):
	((al, ar), (bl, br), (cl, cr)) = (a, b, c)
	return al <= cl <= ar <= cr and al <= bl <= br <= cr

def min_taps(n, radii):
	assert n >= 1
	assert len(radii) == n + 1
	ranges = []
	for (center, radius) in enumerate(radii):
		if radius > 0:
			left_end = max(0, center - radius)
			right_end = min(n, center + radius)
			ranges.append((left_end, right_end))
	ranges = remove_overlap(ranges)
	final_ranges = []
	for rng in ranges:
		if len(final_ranges) >= 2 and union_covers(final_ranges[-2], final_ranges[-1], rng):
			final_ranges.pop()
		final_ranges.append(rng)
	if final_ranges and final_ranges[0][0] == 0 and (final_ranges[-1][-1] == n) and all((final_ranges[i][1] >= final_ranges[i + 1][0] for i in range(len(final_ranges) - 1))):
		return len(final_ranges)
	else:
		return -1

class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		return min_taps(n, ranges)


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		covers = []
		for (i, r) in enumerate(ranges):
			if r == 0:
				continue
			covers.append([max(0, i - r), min(n, i + r)])
		if len(covers) == 0:
			return -1
		covers.sort(key=lambda x: x[0])
		result = 0
		reach = 0
		while len(covers) != 0:
			temp = None
			while len(covers) != 0:
				if covers[0][0] - reach > 0:
					break
				x = covers.pop(0)
				if temp == None or temp[1] < x[1]:
					temp = x
			if temp is None:
				return -1
			result += 1
			reach = temp[1]
			if reach == n:
				break
		return result


(BEGIN, END) = (0, 1)

class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		stitch = max_reach = cnt = i = 0
		clips = sorted(((i - diff, i + diff) for (i, diff) in enumerate(ranges) if diff))
		N = len(clips)
		while max_reach < n:
			while i < N and clips[i][BEGIN] <= stitch:
				max_reach = max(max_reach, clips[i][END])
				i += 1
			if stitch == max_reach:
				return -1
			cnt += 1
			stitch = max_reach
		return cnt


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		(opens, closes, closed) = ([[] for _ in range(n)], [[] for _ in range(n)], set())
		for i in range(len(ranges)):
			idx = 0
			if i - ranges[i] > 0:
				idx = i - ranges[i]
			if idx < len(opens):
				opens[idx].append(i)
			if i + ranges[i] < n:
				closes[i + ranges[i]].append(i)
		(heap, cur_open_tap, res) = ([], None, 0)
		for i in range(n):
			for op in opens[i]:
				heappush(heap, [-(op + ranges[op]), op])
			for cl in closes[i]:
				closed.add(cl)
				if cl == cur_open_tap:
					cur_open_tap = None
			while cur_open_tap is None:
				if not heap:
					return -1
				if heap[0][1] in closed:
					heappop(heap)
				else:
					cur_open_tap = heap[0][1]
					res += 1
		return res


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		max_right = [0] * (n + 1)
		for (i, x) in enumerate(ranges):
			max_right[max(0, i - x)] = max(max_right[max(0, i - x)], i + x)
		i = 0
		best_right = 0
		ans = 0
		j = 0
		while i < n:
			while j <= i:
				best_right = max(max_right[j], best_right)
				j += 1
			if best_right <= i:
				return -1
			ans += 1
			i = best_right
		return ans


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		(r, R) = (0, sorted(([x - r, x + r] for (x, r) in enumerate(ranges))) + [[9 ** 9]])
		did = can = count = 0
		for x in range(n):
			while R[r][0] <= x:
				can = max(can, R[r][1])
				r += 1
			if did == x:
				if can <= x:
					return -1
				did = can
				count += 1
				if did == n:
					break
		return count


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		taps = []
		for (i, r) in enumerate(ranges):
			if r > 0:
				taps.append([max(0, i - r), -min(n, i + r)])
		if not taps:
			return -1
		taps.sort()
		if taps[0][0] != 0:
			return -1
		stack = [[taps[0][0], abs(taps[0][1])]]
		for t in taps[1:]:
			if stack[-1][1] == n:
				break
			(l, r) = (t[0], abs(t[1]))
			if r <= stack[-1][1]:
				continue
			if l > stack[-1][1]:
				return -1
			if len(stack) == 1:
				stack.append([l, r])
			else:
				if l <= stack[-2][1]:
					stack.pop()
				stack.append([l, r])
		return len(stack)


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		needed = [100000] * (n + 1)
		for i in range(len(ranges)):
			l_i = i - ranges[i]
			if l_i <= 0:
				need = 1
			else:
				need = needed[l_i] + 1
			right_most = min(i + ranges[i], len(ranges) - 1)
			while need < needed[right_most] and right_most > i - 1:
				needed[right_most] = need
				right_most -= 1
		if needed[-1] > 10000:
			return -1
		return needed[-1]


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		steps = [0] * (n + 1)
		for (i, r) in enumerate(ranges):
			if i - r < 0:
				steps[0] = max(i + r, steps[0])
			else:
				steps[i - r] = max(i + r, steps[i - r])
		num = 1
		cur = 0
		cur_max = steps[0]
		while cur_max < n:
			next_max = cur_max
			for loc in range(cur + 1, cur_max + 1):
				next_max = max(next_max, steps[loc])
			if next_max == cur_max:
				return -1
			num += 1
			cur = cur_max
			cur_max = next_max
		return num


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		for (i, val) in enumerate(ranges):
			if i - val < 0:
				ranges[0] = max(i + val, ranges[0])
			else:
				ranges[i - val] = max(val * 2, ranges[i - val])
		i = 0
		prev = -1
		counter = 0
		while i != prev:
			distance = ranges[i]
			if i + distance >= n:
				return counter + 1
			maxIndex = i
			for j in range(i + 1, i + distance + 1):
				if j + ranges[j] >= maxIndex + ranges[maxIndex]:
					maxIndex = j
				j += 1
			prev = i
			i = maxIndex
			counter += 1
		return -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		ls = []
		for i in range(n + 1):
			ls.append((max(i - ranges[i], 0), min(i + ranges[i], n + 1)))
		ls.sort(key=lambda x: (x[0], -x[1]))
		(ans, a, b) = (0, -1, 0)
		while b < n:
			(c, d) = ls.pop(0)
			if c > b:
				return -1
			elif d <= b:
				continue
			elif c > a:
				ans += 1
				(a, b) = (b, d)
			elif c <= a:
				b = d
		return ans


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		max_right = [0] * (n + 1)
		for (i, x) in enumerate(ranges):
			l = max(0, i - x)
			r = min(n, i + x)
			max_right[l] = r
		ans = 0
		curr_reach = max_reach = 0
		print(max_right)
		for i in range(n + 1):
			max_reach = max(max_reach, max_right[i])
			if i == curr_reach:
				print((i, curr_reach, max_reach))
				curr_reach = max_reach
				ans += 1
				if curr_reach == n:
					return ans
		return ans if curr_reach >= n else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		for (i, r) in enumerate(ranges):
			left = max(0, i - r)
			right = i + r
			ranges[left] = max(ranges[left], right)
		(r, res) = (0, 0)
		while r < n:
			tmp = r
			r = max(ranges[0:r + 1])
			res += 1
			if tmp == r:
				return -1
		return res


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		if n == 0:
			return 0
		steps = [0] * (n + 1)
		for (i, r) in enumerate(ranges):
			left = max(0, i - r)
			right = min(n, i + r)
			for j in range(left, right + 1):
				steps[j] = right
		res = 1
		prev = 0
		cur = steps[0]
		while cur > prev:
			if cur == n:
				return res
			tmp = cur
			for i in range(prev + 1, cur + 1):
				cur = max(cur, steps[i])
			prev = tmp
			res += 1
		return -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		l = []
		for i in range(n + 1):
			l.append((i - ranges[i], i + ranges[i]))
		l.sort()
		maxlen = 0
		curpos = 0
		res = 0
		while maxlen < n:
			new = maxlen
			while curpos <= n and l[curpos][0] <= maxlen:
				if l[curpos][1] > maxlen:
					new = max(new, l[curpos][1])
				curpos += 1
			if maxlen == new:
				return -1
			res += 1
			maxlen = new
		return res


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		max_range = [0 for i in range(n + 1)]
		for i in range(n + 1):
			(left, right) = (max(0, i - ranges[i]), min(i + ranges[i], n))
			max_range[left] = max(max_range[left], right - left)
		jumps = 0
		(curlen, endlen) = (0, 0)
		print(max_range)
		for i in range(n + 1):
			if max_range[i] == 0 and endlen < i:
				return -1
			curlen = max(curlen, i + max_range[i])
			if i == endlen:
				endlen = curlen
				jumps += 1
			if endlen == n:
				return jumps
		return jumps


class Solution:

	def minTaps(self, n: int, ranges):
		taps = [[max(0, i - ranges[i]), min(n, i + ranges[i])] for i in range(n + 1)]
		taps.sort()
		ans = i = last = 0
		while i < len(taps):
			if last == n:
				return ans
			if taps[i][0] > last:
				return -1 if last < n else ans
			temp = -1
			while i < len(taps) and taps[i][0] <= last:
				temp = max(temp, taps[i][1])
				i += 1
			if temp > last:
				ans += 1
				last = temp
			else:
				return -1
		return ans if last == n else -1


class Solution:

	def minTaps(self, n: int, minjump: List[int]) -> int:
		for i in range(n + 1):
			left = max(0, i - minjump[i])
			right = min(n, i + minjump[i])
			minjump[left] = max(minjump[left], right - left)
		jump = 1
		steps = minjump[0]
		maxreach = minjump[0]
		(lastindex, maxjump) = (0, minjump[0])
		for i in range(1, n + 1):
			steps -= 1
			if steps < 0:
				return -1
			if i + minjump[i] > maxreach:
				maxreach = minjump[i] + i
				maxjump = minjump[i]
				lastindex = i
			if steps == 0 and i != n:
				steps = lastindex + maxjump - i
				jump += 1
		return jump


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		new_ranges = []
		for i in range(len(ranges)):
			new_ranges.append([max(0, i - ranges[i]), min(n, i + ranges[i])])
		new_ranges = sorted(new_ranges, key=lambda x: x[0])
		tap_counter = 0
		ranges_counter = 0
		i = 0
		while i < n:
			max_right = -1
			while ranges_counter < len(new_ranges) and new_ranges[ranges_counter][0] <= i:
				max_right = max(max_right, new_ranges[ranges_counter][1])
				ranges_counter += 1
			if max_right == -1:
				return -1
			tap_counter += 1
			i = max_right
		return tap_counter


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		if len(ranges) == 0:
			return 0
		segments = [(max(0, index - num), min(n, index + num)) for (index, num) in enumerate(ranges)]
		segments = sorted(segments)
		(left, right) = (-1, 0)
		cnt = 0
		for (a, b) in segments:
			if a > right:
				break
			if right == n:
				break
			if right >= a > left:
				cnt += 1
				left = right
			right = max(right, b)
		if right == n:
			return cnt
		return -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		hp = []
		for (i, r) in enumerate(ranges):
			if r != 0:
				heapq.heappush(hp, (max(i - r, 0), -(i + r)))
		ans = []
		while hp:
			(start, end) = heapq.heappop(hp)
			end = -end
			if not ans:
				ans.append((start, end))
			else:
				if start > ans[-1][1]:
					return -1
				if end <= ans[-1][1]:
					continue
				if len(ans) >= 2 and start <= ans[-2][1]:
					ans[-1] = (start, end)
				elif start <= ans[-1][1]:
					ans.append((start, end))
			if ans and ans[-1][1] >= n:
				break
		print(ans)
		return len(ans) if ans and ans[-1][1] >= n else -1


import bisect

class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		uc = 0
		taps = []
		taps_r = []
		for (idx, r) in enumerate(ranges):
			if r > 0:
				tap = (idx - r if idx - r > 0 else 0, idx + r)
				tapr = (idx + r, idx - r if idx - r > 0 else 0)
				taps_r.append(tapr)
				taps.append(tap)
		if not taps:
			return -1
		taps.sort()
		curr_idx = bisect.bisect_left(taps, (1, 0)) - 1
		curr_idx = curr_idx if curr_idx > 0 else 0
		if taps[curr_idx][0] > 0:
			return -1
		e_range = taps[curr_idx][1]
		res = 1
		if e_range >= n:
			return 1
		lo = curr_idx
		hi = len(taps)
		while e_range < n:
			hi = bisect.bisect_left(taps, (e_range + 1, 0), lo, hi)
			print(hi)
			max_e = 0
			for i in range(lo, hi):
				if taps[i][1] > max_e:
					curr_idx = i
					max_e = taps[i][1]
			if max_e <= e_range:
				return -1
			e_range = max_e
			lo = curr_idx
			hi = len(taps)
			res += 1
		return res


class Solution:

	def minTaps(self, n: int, ranges) -> int:

		def process_input(ranges):
			spans = []
			for i in range(len(ranges)):
				spans.append([max(i - ranges[i], 0), i + ranges[i]])
			return spans
		spans = process_input(ranges)
		spans.sort(key=lambda time: (time[0], -time[1]))
		sol = []
		step = 0.5
		for i in range(len(spans)):
			if step > n:
				continue
			if spans[i][0] < step and spans[i][1] > step:
				try:
					if spans[i][0] <= sol[-2][1]:
						sol.pop()
				except:
					pass
				sol.append(spans[i])
				step = spans[i][1] + 0.5
		if step < n:
			return -1
		return len(sol)


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		items = []
		for (i, num) in enumerate(ranges):
			items.append((max(0, i - num), min(i + num, n)))
		res = 0
		right = 0
		items.sort()
		i = 0
		while i < len(items):
			farreach = right
			while i < len(items) and items[i][0] <= right:
				farreach = max(farreach, items[i][1])
				i += 1
			if farreach == right:
				return -1
			res += 1
			if farreach >= n:
				return res
			right = farreach
		return -1


from typing import List, Tuple
from sortedcontainers import SortedSet

class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		intervals = SortedSet()
		for (i, w) in enumerate(ranges):
			newInterval = (max(i - w, 0), min(i + w, n))
			idx = intervals.bisect_left(newInterval)
			if idx < len(intervals) and self.aContainsB(intervals[idx], newInterval):
				continue
			elif idx > 0 and self.aContainsB(intervals[idx - 1], newInterval):
				continue
			else:
				change = True
				while change:
					change = False
					idx = intervals.bisect_left(newInterval)
					if idx < len(intervals) and self.aContainsB(newInterval, intervals[idx]):
						del intervals[idx]
						change = True
					elif idx > 0 and self.aContainsB(newInterval, intervals[idx - 1]):
						del intervals[idx - 1]
						change = True
					elif idx > 1 and self.overlaps(newInterval, intervals[idx - 2]):
						del intervals[idx - 1]
						change = True
				intervals.add(newInterval)
		prevEnd = 0
		for (start, end) in intervals:
			if start > prevEnd:
				return -1
			prevEnd = end
		if end < n:
			return -1
		return len(intervals)

	def aContainsB(self, a: Tuple[int, int], b: Tuple[int, int]) -> bool:
		(a_start, a_end) = a
		(b_start, b_end) = b
		return a_start <= b_start and a_end >= b_end

	def overlaps(self, a: Tuple[int, int], b: Tuple[int, int]) -> bool:
		(a_start, a_end) = a
		(b_start, b_end) = b
		return a_end >= b_start and b_end >= a_start


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		import heapq
		print(len(ranges))
		range_tuples = []
		for (i, val) in enumerate(ranges):
			if val == 0:
				continue
			range_tuples.append((max(0, i - val), min(n, i + val)))
		range_tuples = sorted(range_tuples)
		heap = [(0, 0)]
		for (start_pos, end_pos) in range_tuples:
			while heap and heap[0][0] < start_pos:
				heapq.heappop(heap)
			curr_min_cost = float('inf')
			while heap and heap[0][0] == start_pos:
				cost = heapq.heappop(heap)[1]
				if cost < curr_min_cost:
					curr_min_cost = cost
			if curr_min_cost == float('inf'):
				if not heap:
					return -1
			else:
				heapq.heappush(heap, (start_pos, curr_min_cost))
			curr_min_cost = min([a for (_, a) in heap])
			heapq.heappush(heap, (end_pos, curr_min_cost + 1))
		while heap and heap[0][0] < n:
			heapq.heappop(heap)
		min_cost = float('inf')
		while heap and heap[0][0] == n:
			cost = heap[0][1]
			if cost < min_cost:
				min_cost = cost
			heapq.heappop(heap)
		if min_cost == float('inf'):
			return -1
		return min_cost


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		max_right = [0] * (n + 1)
		for (i, x) in enumerate(ranges):
			l = max(0, i - x)
			r = min(n, i + x)
			max_right[l] = r
		ans = 0
		reach = 0
		while reach < n:
			max_reach = max((r for r in max_right[:reach + 1]))
			if max_reach <= reach:
				return -1
			reach = max_reach
			ans += 1
		return ans


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		open_ranges = sorted([(idx - span, idx + span) for (idx, span) in enumerate(ranges)])
		(start, end, count) = (0, 0, 0)
		i = 0
		while i < len(ranges):
			for j in range(i, len(ranges)):
				(l, r) = open_ranges[j]
				if l <= start:
					if r >= end:
						end = r
						i = j
			count += 1
			if end >= n:
				return count
			if start == end:
				return -1
			start = end


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		max_right = [0] * (n + 1)
		for (i, r) in enumerate(ranges):
			max_right[max(0, i - r)] = max(max_right[max(0, i - r)], min(n, i + ranges[i]))
		dp = [float('inf')] * len(max_right)
		dp[0] = 0
		for (i, x) in enumerate(ranges):
			for j in range(i + 1, max_right[i] + 1):
				dp[j] = min(dp[j], dp[i] + 1)
		return dp[n] if dp[n] != float('inf') else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		(furthest, cnt, cur) = ([0] * n, 0, 0)
		for i in range(n + 1):
			l = max(0, i - ranges[i])
			r = min(n, i + ranges[i])
			for j in range(l, r):
				furthest[j] = max(furthest[j], r)
		while cur < n:
			if furthest[cur] == 0:
				return -1
			cur = furthest[cur]
			cnt += 1
		return cnt


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		intervals = []
		for (i, r) in enumerate(ranges):
			intervals.append((i - r if i - r > 0 else 0, i + r))
		intervals.sort(key=lambda t: (t[0], -t[1]))
		l = len(intervals)
		i = 0
		ans = 1
		while i < l:
			if intervals[i][1] >= n:
				return ans
			right = -1
			next_i = -1
			for j in range(i + 1, l):
				if intervals[j][0] <= intervals[i][1] and intervals[j][1] >= right:
					right = intervals[j][1]
					next_i = j
			if next_i == -1:
				return -1
			ans += 1
			i = next_i
		return ans


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		best = [float('inf') for _ in ranges]
		for (i, r) in enumerate(ranges):
			if r > 0:
				(start, end) = (i - r, i + r)
				best_with = 1 + (best[start] if start > 0 else 0)
				for j in range(max(0, start), min(len(ranges), end + 1)):
					best[j] = min(best[j], best_with)
		if any((v for v in best if v == float('inf'))):
			return -1
		return best[-1]


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		if n < 1 or ranges is None:
			return -1
		dp = [None] * len(ranges)
		for i in range(len(dp)):
			l = max(0, i - ranges[i])
			r = min(len(dp) - 1, i + ranges[i])
			for j in range(l, r + 1):
				if dp[j] is None:
					dp[j] = l
				else:
					dp[j] = min(dp[j], l)
			if dp[-1] == 0:
				return 1
		i = len(dp) - 1
		c = 0
		while i > 0 and dp[i] is not None and (dp[i] != i):
			i = dp[i]
			c += 1
		return c if i == 0 else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		inf = 1 << 50
		prev = collections.defaultdict(lambda : inf)
		for (i, r) in enumerate(ranges):
			prev[min(i + r, n)] = min(prev[min(i + r, n)], max(i - r, 0))
		dp = [inf] * (n + 1)
		dp[0] = 0
		for x in range(n + 1):
			for y in range(prev[x], x):
				dp[x] = min(dp[y] + 1, dp[x])
		res = dp[n]
		if res >= inf:
			return -1
		return res


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for cur in range(n + 1):
			left = max(0, cur - ranges[cur] + 1)
			right = min(n, cur + ranges[cur])
			lastend = max(0, cur - ranges[cur])
			for idx in range(left, right + 1):
				dp[idx] = min(dp[idx], dp[lastend] + 1)
		return dp[-1] if dp[-1] < float('inf') else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [-1 for x in range(n + 1)]
		for i in range(n + 1):
			minId = max(0, i - ranges[i])
			maxId = min(n, i + ranges[i])
			for i in range(minId, maxId + 1):
				dp[i] = max(dp[i], maxId)
		if dp[0] == -1:
			return -1
		maxReach = dp[0]
		count = 1
		while maxReach < n:
			nxt = dp[maxReach]
			if nxt == maxReach:
				return -1
			maxReach = nxt
			count += 1
		return count


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		full_ranges = []
		for i in range(n + 1):
			r = (i - ranges[i], i + ranges[i])
			full_ranges.append(r)
		full_ranges.sort()
		range_idx = 0
		covered_max = 0
		num_taps = 0
		while covered_max < n and range_idx < len(full_ranges):
			if full_ranges[range_idx][0] > covered_max:
				return -1
			furthest = -1
			while range_idx < len(full_ranges) and full_ranges[range_idx][0] <= covered_max:
				furthest = max(furthest, full_ranges[range_idx][1])
				range_idx += 1
			assert furthest != -1
			num_taps += 1
			covered_max = furthest
		if covered_max < n:
			return -1
		else:
			return num_taps


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		max = 0
		min = 0
		index = 0
		total = 0
		while max < n:
			for i in range(index, len(ranges)):
				left = i - ranges[i]
				right = i + ranges[i]
				if left <= min and right > max:
					max = right
					index = i
			if min == max:
				return -1
			total += 1
			min = max
		return total


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		rangesCovered = {}
		for (i, ran) in enumerate(ranges):
			if ran == 0:
				continue
			rangesCovered[i] = (max(0, i - ranges[i]), min(n, i + ranges[i]))
		dp = [n + 2] * (n + 1)
		dp[0] = 0
		for curRange in list(rangesCovered.values()):
			startInd = curRange[0]
			endInd = curRange[1]
			for i in range(startInd + 1, endInd + 1):
				dp[i] = min(dp[i], dp[startInd] + 1)
		if dp[n] == n + 2:
			return -1
		else:
			return dp[n]


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		cover = [math.inf] * n
		for (i, r) in enumerate(ranges):
			start = max(i - r, 0)
			end = min(i + r, n)
			pre_min = cover[start - 1] if start > 0 else 0
			for j in range(start, end):
				cover[j] = min(cover[j], 1 + pre_min)
		return cover[-1] if cover[-1] != math.inf else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [sys.maxsize] * (n + 1)
		dp[0] = 0
		for (i, tmp) in enumerate(ranges):
			left = max(0, i - tmp)
			right = min(n, i + tmp)
			for j in range(left, right + 1):
				dp[j] = min(dp[j], dp[left] + 1)
		return dp[n] if dp[n] < sys.maxsize else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		rangelist = [None] * (n + 1)
		for i in range(n + 1):
			s = max(i - ranges[i], 0)
			e = min(i + ranges[i], n)
			if rangelist[s] == None:
				rangelist[s] = (s, e)
			else:
				rangelist[s] = (s, max(rangelist[s][1], e))
		curr = mx = 0
		count = 0
		i = 0
		while i < len(rangelist):
			while True and i < len(rangelist):
				if rangelist[i] == None:
					i += 1
					continue
				(s, e) = rangelist[i]
				if s > mx:
					return -1
				if s > curr:
					break
				mx = max(e, mx)
				i += 1
			if curr != mx:
				curr = mx
				count += 1
		if mx < n:
			return -1
		return count


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [float('inf')] * (n + 1)
		for i in range(len(ranges)):
			if i - ranges[i] <= 0:
				taps = 1
			else:
				taps = dp[i - ranges[i]] + 1
			lo = max(i - ranges[i], 0)
			hi = min(i + ranges[i], n)
			for j in range(lo, hi + 1):
				dp[j] = min(dp[j], taps)
		return dp[-1] if dp[-1] != float('inf') else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		arr = [float('inf') for _ in range(n + 1)]
		arr[0] = 0
		i = 0
		while i < len(arr):
			left = max(0, i - ranges[i])
			right = min(len(arr) - 1, i + ranges[i])
			j = left + 1
			while j <= right:
				arr[j] = min(arr[j], 1 + arr[left])
				j += 1
			i += 1
		if arr[-1] == float('inf'):
			return -1
		return arr[-1]


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [n for _ in range(n + 1)]
		for (index, ranged) in enumerate(ranges):
			start = max(0, index - ranged)
			end = min(n, index + ranged)
			if start == 0:
				extra = 0
			else:
				extra = dp[start]
			for i in range(start + 1, end + 1):
				dp[i] = min(dp[i], 1 + extra)
		if dp[-1] != n:
			return dp[-1]
		else:
			return -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		intervals = []
		for (i, r) in enumerate(ranges):
			intervals.append([i - r, i + r])
		intervals.sort(key=lambda x: [x[0], -x[1]])
		count = 0

		def getnext(l):
			rel = []
			for i in intervals:
				if l >= i[0] and l < i[1]:
					rel.append(i)
			rel.sort(key=lambda x: x[1], reverse=True)
			return rel[0] if rel else None
		j = 0
		while j < n:
			iv = getnext(j)
			if iv:
				j = iv[1]
				count += 1
			else:
				return -1
		return count


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		intervals = []
		for (i, x) in enumerate(ranges):
			intervals.append([i - x, i + x])

		def mySortKey(x):
			left = x[0]
			if left <= 0:
				left = 0
			right = x[1]
			return left * 100 - right
		intervals.sort(key=mySortKey)
		print(intervals)
		greedyFurthest = intervals[0][1]
		nextGreedyFurthest = 0
		j = 0
		count = 1
		while j < len(intervals):
			connect = False
			if greedyFurthest >= n:
				return count
			while j < len(intervals) and intervals[j][0] <= greedyFurthest:
				if intervals[j][1] > nextGreedyFurthest:
					nextGreedyFurthest = intervals[j][1]
				j += 1
				connect = True
			greedyFurthest = nextGreedyFurthest
			count += 1
			if not connect:
				return -1
		if greedyFurthest >= n:
			return count
		else:
			return -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		coords = []
		for (i, rng) in enumerate(ranges):
			if not rng:
				continue
			coords.append([max(0, i - rng), min(i + rng, n)])
		coords.sort()
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for [start, end] in coords:
			if start > n:
				break
			prev = dp[start]
			for i in range(start, min(end, n)):
				dp[i + 1] = min(prev + 1, dp[i + 1])
		return dp[-1] if dp[-1] < float('inf') else -1


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [float('inf')] * (n + 1)
		dp[0] = 0
		for i in range(n + 1):
			L = max(0, i - ranges[i])
			R = min(n, i + ranges[i])
			for j in range(L + 1, R + 1):
				dp[j] = min(dp[j], dp[L] + 1)
		if dp[n] >= n + 2:
			return -1
		return dp[-1]


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		areas = [(x - ranges[x], x + ranges[x]) for x in range(n + 1)]
		areas = sorted(areas, key=lambda x: x[0])

		def get_intersections(current, intervals):
			results = []
			for interval in intervals:
				if current[0] <= interval[0] <= current[1] and interval[1] > current[1]:
					results.append(interval)
			return results
		first = areas[0]
		for intersection in areas:
			if intersection[0] <= 0 and intersection[1] > first[1]:
				first = intersection
		selected = [first]
		area_to_cover = (first[1], n)
		while area_to_cover[0] < area_to_cover[1]:
			prev = selected[-1]
			intersections = get_intersections(prev, areas)
			if len(intersections) is 0:
				return -1
			intersections = sorted(intersections, key=lambda x: x[1])
			rightmost = intersections[-1]
			if rightmost[1] < area_to_cover[0]:
				return -1
			selected.append(rightmost)
			area_to_cover = (rightmost[1], n)
		return len(selected)


class Solution:

	def minTaps(self, n: int, ranges: List[int]) -> int:
		dp = [n + 2] * (n + 1)
		dp[0] = 0
		for i in range(n + 1):
			start = max(0, i - ranges[i])
			end = min(n, i + ranges[i])
			for j in range(start, end + 1):
				dp[j] = min(dp[j], dp[start] + 1)
		if dp[n] == n + 2:
			return -1
		return dp[n]