Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/871.html
871. Minimum Number of Refueling Stops
Level
Hard
Description
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^90 <= stations.length <= 5000 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target
Solution
Create a priority queue to store the liters of gas at each gas station, where the maximum element is polled from the priority queue first.
Each time try to reach the next gas station without refueling. If it is impossible, then each time poll one element from the priority queue and add it to the car’s total fuel until the next gas station can be reached. After the last gas station, the car needs to reach the target, so apply the operation for the target as well. If at one point the car can never reach the next gas station or the target, return -1. Otherwise, return the number of times of refueling.
-
class Solution { public int minRefuelStops(int target, int startFuel, int[][] stations) { PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer num1, Integer num2) { return num2 - num1; } }); int refuels = 0; int remain = startFuel; int prevPosition = 0; int length = stations.length; for (int i = 0; i < length; i++) { int[] station = stations[i]; int position = station[0], gas = station[1]; remain -= position - prevPosition; while (!priorityQueue.isEmpty() && remain < 0) { remain += priorityQueue.poll(); refuels++; } if (remain < 0) return -1; priorityQueue.offer(gas); prevPosition = position; } remain -= target - prevPosition; while (!priorityQueue.isEmpty() && remain < 0) { remain += priorityQueue.poll(); refuels++; } if (remain < 0) return -1; else return refuels; } } -
// OJ: https://leetcode.com/problems/minimum-number-of-refueling-stops/ // Time: O(N^2) // Space: O(N^2) class Solution { public: int minRefuelStops(int target, int startFuel, vector<vector<int>>& A) { int N = A.size(); vector<vector<long>> dp(N + 1, vector<long>(N + 1)); for (int i = 0; i <= N; ++i) dp[i][0] = startFuel; for (int i = 0; i < N; ++i) { for (int j = 1; j <= i + 1; ++j) { dp[i + 1][j] = max(dp[i][j - 1] >= A[i][0] ? dp[i][j - 1] + A[i][1] : 0, dp[i][j]); } } for (int i = 0; i <= N; ++i) { if (dp[N][i] >= target) return i; } return -1; } }; -
class Solution: def minRefuelStops( self, target: int, startFuel: int, stations: List[List[int]] ) -> int: q = [] prev = ans = 0 stations.append([target, 0]) for a, b in stations: d = a - prev startFuel -= d while startFuel < 0 and q: startFuel -= heappop(q) ans += 1 if startFuel < 0: return -1 heappush(q, -b) prev = a return ans ############ class Solution(object): def minRefuelStops(self, target, startFuel, stations): """ :type target: int :type startFuel: int :type stations: List[List[int]] :rtype: int """ # [pos, fuel] stations.append([target, float("inf")]) # -fuel que = [] pos = 0 tank = startFuel res = 0 prev = 0 for p, g in stations: tank -= p - prev while que and tank < 0: tank += -heapq.heappop(que) res += 1 if tank < 0: return -1 heapq.heappush(que, -g) prev = p return res -
func minRefuelStops(target int, startFuel int, stations [][]int) int { stations = append(stations, []int{target, 0}) ans, prev := 0, 0 q := &hp{} heap.Init(q) for _, s := range stations { d := s[0] - prev startFuel -= d for startFuel < 0 && q.Len() > 0 { startFuel += q.pop() ans++ } if startFuel < 0 { return -1 } q.push(s[1]) prev = s[0] } return ans } type hp struct{ sort.IntSlice } func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] } func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() interface{} { a := h.IntSlice v := a[len(a)-1] h.IntSlice = a[:len(a)-1] return v } func (h *hp) push(v int) { heap.Push(h, v) } func (h *hp) pop() int { return heap.Pop(h).(int) }