Algorithm & Data Structure - Minimum Number of Refuel Stops
Problem Statement
Approach 1 - dynamic programming:
Let \(n\) be the size of stations, the maiximum refuel could be \(n\), and the minimum refuel could be 0; Let \(dp[i]\) be the maximum miles with \(i\) refuels. For every stations, if it is in the range of \(dp[i]\), then we could refuel, and it is added to \(dp[i+1]\). We need to find the maximum of \(dp[i+1]\).
public int minRefuelStops(int target, int startFuel, int[][] stations) {
int n = stations.length;
int [] dp = new int[n+1];
dp[0] = startFuel;
for (int i = 0; i < n; i++)
for (int j = i; j >= 0; j--) {
if (stations[i][0] <= dp[j]) {
dp[j+1] = Math.max(dp[j+1], dp[j] + stations[i][1]);
}
}
for (int i = 0 ; i <= n; i++)
if (dp[i] >= target) return i;
return -1;
}
Approach 2 - Heap method:
Like in approach 1, we are looking for the maximum miles we can get with least refuels. Suppose we are at a position and we lost all fuels, we want to know where could we refuel before to reach the maximum distance. So we need to store all previous fuels and find the maximum one to refuel. Whenever we are at a position, we store all reachable stations’ fuel into a heap, and when we reach a location with shortage of fuel, we go back to get the maximum fuel from the heap.
public int minRefuelStops(int target, int startFuel, int[][] stations) {
int n = stations.length;
PriorityQueue<Integer> pq = new PriorityQueue<>((x,y)->-1*Integer.compare(x,y));
int i = 0;
int count = 0;
int curMax = startFuel; //current maximum mileage
while (curMax < target) {
// with last refuel, the maixmum stations we can reach and store their fuel to PQ
while (i < n && curMax >= stations[i][0]) {
pq.offer(stations[i++][1]);
}
//jump out when we reach the limit that curMax could reach.
// if we are not able to get any fuel, we are done
if (pq.isEmpty()) return -1;
// get the maximum fuel from previous stored fuel
curMax += pq.poll();
count++;
}
return count;
}