A car travels from a starting position to a destination which is target miles east of the starting position.
Along the way, there are gas stations.  Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.
The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it.  It uses 1 liter of gas per 1 mile that it drives.
When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.
What is the least number of refueling stops the car must make in order to reach its destination?  If it cannot reach the destination, return -1.
Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there.  If the car reaches the destination with 0 fuel left, it is still considered to have arrived.
 

Example 1:
Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.


Example 2:
Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can't reach the target (or even the first gas station).


Example 3:
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: 
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel.  We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas.  We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

 
Note:

1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		heap = []
		stop = 0
		dist = startFuel
		for (d, g) in stations:
			if dist >= target:
				return stop
			while heap and dist < d:
				gas = heapq.heappop(heap)
				dist += -gas
				stop += 1
			if dist < d:
				return -1
			heapq.heappush(heap, -g)
		if dist >= target:
			return stop
		while heap:
			g = heapq.heappop(heap)
			stop += 1
			dist += -g
			if dist >= target:
				return stop
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		if not stations:
			return -1
		fdelta = startFuel - stations[0][0]
		if fdelta < 0:
			return -1
		curr = [fdelta + stations[0][1], fdelta]
		for (i, sta) in enumerate(stations[1:]):
			treck = sta[0] - stations[i][0]
			leftover = curr[0] - treck
			if leftover < 0:
				return -1
			nex = [leftover + sta[1], leftover]
			for (j, f) in enumerate(curr[1:]):
				leftover = curr[j + 1] - treck
				if leftover < 0:
					break
				else:
					nex[-1] = max(nex[-1], leftover + sta[1])
					nex.append(leftover)
			curr = nex
		leftover = target - stations[-1][0]
		while curr and curr[-1] < leftover:
			curr.pop()
		return len(stations) - len(curr) + 1 if curr else -1


import heapq

class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		stops = 0
		max_gas_heap = []
		can_drive_to = startFuel
		i = 0
		while can_drive_to < target:
			while i < len(stations) and stations[i][0] <= can_drive_to:
				heapq.heappush(max_gas_heap, -stations[i][1])
				i += 1
			if not max_gas_heap:
				return -1
			can_drive_to -= heapq.heappop(max_gas_heap)
			stops += 1
		return stops


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		n = len(stations)
		dp = [0] * (n + 1)
		dp[0] = startFuel
		for i in range(1, n + 1):
			for j in range(i, 0, -1):
				if dp[j - 1] >= stations[i - 1][0]:
					dp[j] = max(dp[j], dp[j - 1] + stations[i - 1][1])
		for i in range(1, n + 1):
			if dp[i] >= target:
				return i
		return -1


import heapq

class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		point = 0
		level = 0
		gas = startFuel
		if gas >= target:
			return level
		heap = []
		stations.append([target + 1, float('inf')])
		for (pos, gas_add) in stations:
			if gas >= pos:
				heapq.heappush(heap, -gas_add)
			else:
				while heap:
					gasmin = heapq.heappop(heap)
					gas -= gasmin
					level += 1
					if gas >= target:
						return level
					if gas >= pos:
						heapq.heappush(heap, -gas_add)
						break
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		if startFuel < target and (not stations):
			return -1
		dp = [startFuel] + [0] * len(stations)
		for (i, val) in enumerate(stations):
			for t in range(i, -1, -1):
				if dp[t] >= val[0]:
					dp[t + 1] = max(dp[t + 1], dp[t] + val[1])
		for (i, d) in enumerate(dp):
			if d >= target:
				return i
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		length = len(stations)
		dp = [startFuel] + [0] * length
		result = float('inf')
		for i in range(1 + length):
			for j in range(i, 0, -1):
				if dp[j - 1] >= stations[i - 1][0]:
					dp[j] = max(dp[j], dp[j - 1] + stations[i - 1][1])
				if dp[j] >= target:
					result = min(result, j)
		return -1 if result == float('inf') else result


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		pq = []
		minStops = i = 0
		curr = startFuel
		while curr < target:
			while i < len(stations) and curr >= stations[i][0]:
				heapq.heappush(pq, -stations[i][1])
				i += 1
			if not pq:
				return -1
			curr += -heapq.heappop(pq)
			minStops += 1
		return minStops


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		from heapq import heapify, heappop, heappush
		dis = startFuel
		heap = []
		stations = stations[::-1]
		while stations and stations[-1][0] <= dis:
			s = stations.pop()
			heap.append((-s[1], s[0]))
		heapify(heap)
		stops = 0
		while heap:
			most_fuel = heappop(heap)
			stops += 1
			dis += -most_fuel[0]
			if dis >= target:
				return stops
			while stations and stations[-1][0] <= dis:
				s = stations.pop()
				heappush(heap, (-s[1], s[0]))
		return -1


class Solution:

	def minRefuelStops(self, target, startFuel, stations):
		stations.append([target, 0])
		stations.sort(reverse=True)
		(curr, tank) = (0, startFuel)
		ans = 0
		refuels = []
		while curr + tank < target:
			(pos, gas) = stations.pop()
			if pos <= curr + tank:
				heapq.heappush(refuels, -gas)
			else:
				curr += tank
				tank = 0
				while curr + tank < pos and refuels:
					ans += 1
					tank -= heapq.heappop(refuels)
				if curr + tank < pos:
					return -1
				heapq.heappush(refuels, -gas)
		return ans


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		q = []
		extent = startFuel
		ans = 0
		for i in range(len(stations)):
			if extent >= target:
				return ans
			(loc, fuel) = stations[i]
			while q and loc > extent:
				extent += -heapq.heappop(q)
				ans += 1
			if loc > extent:
				return -1
			heapq.heappush(q, -fuel)
		while q and extent < target:
			extent += -heapq.heappop(q)
			ans += 1
		if extent >= target:
			return ans
		else:
			return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		pq = []
		idx = 0
		cur = startFuel
		res = 0
		while cur < target:
			while idx < len(stations) and cur >= stations[idx][0]:
				heapq.heappush(pq, -stations[idx][1])
				idx += 1
			if not pq:
				return -1
			cur -= heapq.heappop(pq)
			res += 1
		return res


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		heap = []
		queue = deque()
		i = 0
		num_stations = 0
		while startFuel < target:
			while i < len(stations) and startFuel >= stations[i][0]:
				heapq.heappush(heap, -stations[i][1])
				i += 1
			if not heap:
				return -1
			next_fuel = heapq.heappop(heap)
			startFuel -= next_fuel
			num_stations += 1
		return num_stations


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		N = len(stations)
		prev_memo = [startFuel] * (N + 1)
		for num_stops in range(1, N + 1):
			memo = [-1] * (N + 1)
			a = -1
			for num_stations in range(num_stops, N + 1):
				(station_mile, station_fuel) = stations[num_stations - 1]
				b = prev_memo[num_stations - 1]
				if b >= station_mile:
					a = max(a, b + station_fuel)
				if a != -1:
					memo[num_stations] = a
			if a >= target:
				return num_stops
			prev_memo = memo
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		stations.sort(reverse=True)
		fuel = startFuel
		heap = []
		out = 0
		while stations:
			while stations and fuel >= stations[-1][0]:
				(t, val) = stations.pop()
				if t >= target:
					return out
				heapq.heappush(heap, -val)
			if heap:
				fuel -= heapq.heappop(heap)
				out += 1
				if fuel >= target:
					return out
			else:
				break
		while heap and fuel < target:
			fuel -= heapq.heappop(heap)
			out += 1
		if fuel < target:
			return -1
		return out


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if target <= startFuel:
			return 0
		dpRefuels = [-1] * len(stations)
		for i in range(len(stations)):
			if stations[i][0] <= startFuel:
				dpRefuels[i] = stations[i][1] + startFuel
				if dpRefuels[i] >= target:
					return 1
		for k in range(1, len(stations)):
			maxPrevFuel = dpRefuels[k - 1]
			for i in range(k, len(stations)):
				temp = max(maxPrevFuel, dpRefuels[i])
				if maxPrevFuel >= stations[i][0]:
					dpRefuels[i] = maxPrevFuel + stations[i][1]
				if dpRefuels[i] >= target:
					return k + 1
				maxPrevFuel = temp
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		fuel = startFuel
		del startFuel
		i = 0
		while target > fuel:
			target -= fuel
			stations = [[dist - fuel, gas] for (dist, gas) in stations]
			try:
				(j, fuel) = max([[j, gas] for (j, (dist, gas)) in enumerate(stations) if dist <= 0], key=lambda stop: stop[1])
			except ValueError:
				return -1
			if fuel == 0:
				return -1
			stations[j][1] = 0
			i += 1
		return i


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		if not stations:
			return -1
		data = []
		for k in range(len(stations)):
			data.append([stations[k][0] - (stations[k - 1][0] if k > 0 else 0), stations[k][1]])
		data.append([target - stations[-1][0], 0])
		tot = startFuel
		for (dist, gas) in data:
			tot -= dist
			if tot < 0:
				return -1
			tot += gas
		N = len(data)
		maxFuel = [float('-inf')] * N
		tot = startFuel
		for k in range(N):
			(dist, _) = data[k]
			tot -= dist
			if tot < 0:
				break
			maxFuel[k] = tot
		nextMaxFuel = [float('-inf')] * N
		nextMaxFuel[0] = maxFuel[0] + data[0][1]
		for k in range(1, N):
			(dist, gas) = data[k]
			if maxFuel[k] != float('-inf'):
				nextMaxFuel[k] = maxFuel[k] + gas
			if nextMaxFuel[k - 1] >= dist:
				nextMaxFuel[k] = max(nextMaxFuel[k], nextMaxFuel[k - 1] - dist)
			if nextMaxFuel[k] == float('-inf'):
				break
		if nextMaxFuel[-1] >= 0:
			return 1
		maxFuel = nextMaxFuel
		for nStops in range(2, N + 1):
			nextMaxFuel = [float('-inf')] * N
			for k in range(nStops - 1, N):
				(dist, gas) = data[k]
				if maxFuel[k - 1] != float('-inf') and maxFuel[k - 1] >= dist:
					nextMaxFuel[k] = maxFuel[k - 1] - dist + gas
				if nextMaxFuel[k - 1] >= dist:
					nextMaxFuel[k] = max(nextMaxFuel[k], nextMaxFuel[k - 1] - dist)
				if nextMaxFuel[k] == float('-inf'):
					break
			if nextMaxFuel[-1] >= 0:
				return nStops
			maxFuel = nextMaxFuel
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		stations = [[0, startFuel]] + sorted(stations)
		n = len(stations)
		reach = [-float('inf')] * n
		reach[0] = startFuel
		st = [startFuel] * n
		flag = True
		cnt = 0
		if target <= startFuel:
			return 0
		while flag:
			flag = False
			cnt += 1
			for i in range(1, len(reach))[::-1]:
				(p, g) = stations[i]
				st.pop()
				if p <= st[-1] and st[-1] + g > reach[i]:
					reach[i] = st[-1] + g
					flag = True
					if reach[i] >= target:
						return cnt
			for i in range(1, len(reach)):
				st.append(max(st[-1], reach[i]))
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		dp = [[startFuel, []]]
		for i in range(len(stations)):
			if dp[-1][0] >= target:
				break
			usedStations = dp[-1][1]
			usable_stations = [s for s in stations if s[0] <= dp[-1][0] and s[0] not in usedStations]
			usable_stations.sort(key=lambda x: x[1])
			if len(usable_stations) == 0:
				break
			dp.append([dp[-1][0] + usable_stations[-1][1], dp[-1][1].copy()])
			dp[-1][1].append(usable_stations[-1][0])
		return len(dp) - 1 if dp[-1][0] >= target else -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		n = len(stations)
		dp = [[0] * (n + 1) for _ in range(n + 1)]
		for row in dp:
			row[0] = startFuel
		if startFuel >= target:
			return 0
		for refuels in range(1, n + 1):
			for stas in range(refuels, n + 1):
				station = stations[stas - 1]
				dp[stas][refuels] = dp[stas - 1][refuels]
				if dp[stas - 1][refuels - 1] >= station[0]:
					dp[stas][refuels] = max(station[1] + dp[stas - 1][refuels - 1], dp[stas][refuels])
			if dp[n][refuels] >= target:
				return refuels
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		return self.dp(target, startFuel, stations)

	def dp(self, target, startFuel, stations):
		if startFuel >= target:
			return 0
		if not stations:
			return -1
		n = len(stations)
		A = [[0] * (n + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			A[0][i] = startFuel
		for t in range(1, n + 1):
			for i in range(1, n + 1):
				if t <= i:
					A[t][i] = A[t][i - 1]
					if A[t - 1][i - 1] >= stations[i - 1][0]:
						A[t][i] = max(A[t][i], A[t - 1][i - 1] + stations[i - 1][1])
			if A[t][-1] >= target:
				return t
		return -1

	def rec1(self, target, startFuel, stations, position, station_idx_start):
		if position >= target or startFuel >= target - position:
			return 0
		else:
			candidates = []
			for idx in range(station_idx_start, len(stations)):
				(p, f) = stations[idx]
				d = p - position
				valid = d > 0 and startFuel - d >= 0
				if valid:
					candidates.append(1 + self.rec(target, startFuel - d + f, stations, p, station_idx_start + 1))
				if startFuel - d < 0:
					break
			if not candidates:
				return float('inf')
			else:
				return min(candidates)


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if target <= startFuel:
			return 0
		stations = [[0, startFuel]] + stations
		print(stations)
		N = len(stations)
		f = [startFuel - stations[i][0] for i in range(N)]
		f[0] = startFuel
		print(f)
		for j in range(N):
			g = [-1] * N
			g[0] = f[0]
			for i in range(N - 1, 0, -1):
				if f[i - 1] - (stations[i][0] - stations[i - 1][0]) >= 0:
					g[i] = f[i - 1] + stations[i][1] - (stations[i][0] - stations[i - 1][0])
			for i in range(1, N):
				g[i] = max(g[i - 1] - (stations[i][0] - stations[i - 1][0]), g[i])
			f = g
			if f[-1] >= target - stations[-1][0]:
				return j + 1
		return -1


class Solution:

	def minRefuelStops(self, t: int, f: int, st: List[List[int]]) -> int:
		if f >= t:
			return 0
		if st == []:
			return -1
		if f < st[0][0]:
			return -1
		(li, li1) = ([], [])
		for (i, j) in st:
			li.append(i)
			li1.append(j)
		count = 0
		while f < t:
			(s, tur) = (0, [])
			for i in li:
				if f >= i:
					s = li.index(i)
					tur.append(True)
				else:
					tur.append(False)
			print(tur)
			if all((i == False for i in tur)):
				return -1
			f += max(li1[0:s + 1])
			li.pop(li1.index(max(li1[0:s + 1])))
			li1.remove(max(li1[0:s + 1]))
			count += 1
		return count


from functools import lru_cache

class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:

		@lru_cache(None)
		def farthest_of_first_n_with_stops(n, stops):
			if n == 0 or stops == 0:
				return startFuel
			dont_refuel_now = farthest_of_first_n_with_stops(n - 1, stops)
			refuel_now = farthest_of_first_n_with_stops(n - 1, stops - 1)
			(x, fuel) = stations[n - 1]
			if refuel_now < x:
				return dont_refuel_now
			else:
				return max(dont_refuel_now, fuel + refuel_now)
		for stops in range(len(stations) + 1):
			if farthest_of_first_n_with_stops(len(stations), stops) >= target:
				return stops
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:

		@lru_cache(maxsize=None)
		def solve(s: int, stops: int) -> int:
			if stops == 0 or s < 0:
				return startFuel
			return max(solve(s - 1, stops), sub + stations[s][1] if (sub := solve(s - 1, stops - 1)) >= stations[s][0] else 0)
		for i in range(len(stations) + 1):
			if solve(len(stations) - 1, i) >= target:
				return i
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		if not stations:
			return -1
		import heapq
		queue = [-f for (i, f) in stations if i <= startFuel]
		heapq.heapify(queue)
		fuel = startFuel
		start = max([i for i in range(len(stations)) if stations[i][0] <= startFuel] + [-1]) + 1
		result = 0
		while queue and fuel < target:
			fuel -= heapq.heappop(queue)
			result += 1
			while start < len(stations) and fuel >= stations[start][0]:
				heapq.heappush(queue, -stations[start][1])
				start += 1
		return result if fuel >= target else -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if target == startFuel:
			return 0
		stations = [startFuel] + stations
		dp = [0] * len(stations)
		dp[0] = startFuel
		for i in range(1, len(stations)):
			j = i - 1
			while j >= 0:
				totalFuel = dp[j] + stations[i][1]
				if dp[j] >= stations[i][0] and totalFuel >= dp[j + 1]:
					dp[j + 1] = totalFuel
				j -= 1
		for (i, fuel) in enumerate(dp):
			if fuel >= target:
				return i
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if target <= startFuel:
			return 0
		if not stations:
			return -1
		dp = [startFuel]
		stops = 0
		lastd = 0
		for (d, fuel) in stations:
			for i in range(stops, len(dp)):
				dp[i] -= d - lastd
				if dp[i] < 0:
					stops = i + 1
			if stops == len(dp):
				return -1
			dp.append(dp[-1] + fuel)
			for i in range(len(dp) - 2, stops, -1):
				dp[i] = max(dp[i], dp[i - 1] + fuel)
			if dp[stops] >= target - d:
				return stops
			lastd = d
		while stops < len(dp):
			if dp[stops] >= target - lastd:
				return stops
			stops += 1
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		if startFuel >= target:
			return 0
		heap = []
		for (d, g) in stations:
			heapq.heappush(heap, (-g, d))
		dist = startFuel
		stop = 0
		dist = startFuel
		tmp = []
		while heap:
			(g, d) = heapq.heappop(heap)
			if d <= dist:
				dist += -g
				if dist >= target:
					return stop + 1
				for el in tmp:
					heapq.heappush(heap, el)
				tmp = []
				stop += 1
			else:
				tmp.append((g, d))
		return -1


class Solution:

	def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
		stations = [[0, 0]] + stations
		heap = [(0, 0, -startFuel)]
		seen = {}
		while heap:
			(stop, pos, fuel) = heappop(heap)
			pos = -pos
			fuel = -fuel
			if pos in seen and seen[pos] >= fuel:
				continue
			seen[pos] = fuel
			if stations[pos][0] + fuel >= target:
				return stop
			if pos + 1 < len(stations) and fuel >= stations[pos + 1][0] - stations[pos][0]:
				new_fuel = fuel - (stations[pos + 1][0] - stations[pos][0])
				heappush(heap, (stop + 1, -(pos + 1), -(new_fuel + stations[pos + 1][1])))
				heappush(heap, (stop, -(pos + 1), -new_fuel))
		return -1