Massive Algorithms: LeetCode 871 - Minimum Number of Refueling Stops

LeetCode 871 - Minimum Number of Refueling Stops

https://leetcode.com/problems/minimum-number-of-refueling-stops/

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

X. PQ
https://leetcode.com/problems/minimum-number-of-refueling-stops/discuss/149867/Simple-Java-using-pq-with-explanation

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    int curFarthest = startFuel, refuel = 0;
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    for (int[] station : stations) {
        // check if we can reach this station
        // if we cannot reach this station, refuel the gas from the previous station with most gas
        // redo the operation until we get enough gas to reach this station
        while (curFarthest < station[0]) {
            if (pq.isEmpty()) return -1; // if we reful in each station but still cannot reach this station, return -1
            curFarthest += pq.poll();
            refuel++;
        }
        pq.offer(station[1]);
    }
    // now we have reached the last station, check if we can reach the target
    while (curFarthest < target) {
        if (pq.isEmpty()) return -1;
        curFarthest += pq.poll();
        refuel++;
    }
    return refuel;
}

http://bookshadow.com/weblog/2018/07/15/leetcode-minimum-number-of-refueling-stops/
public int minRefuelStops(int target, int startFuel, int[][] stations) { PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); int loc = 0, stop = 0, fuel = startFuel; for (int[] st : stations) { if (fuel + loc >= target) { return stop; } int sloc = st[0], sfuel = st[1]; while (!pq.isEmpty() && fuel < sloc - loc) { fuel += pq.poll(); stop += 1; } if (fuel < sloc - loc) { return -1; } fuel -= sloc - loc; pq.add(sfuel); loc = sloc; } while (!pq.isEmpty() && fuel < target - loc) { fuel += -pq.poll(); stop += 1; } return fuel < target - loc ? -1 : stop; }
https://leetcode.com/problems/minimum-number-of-refueling-stops/discuss/149839/DP-O(N2)-and-Priority-Queue-O(NlogN)
Approach 2: Priority Queue, O(NlogN)

i is the index of next stops to refuel.
res is the times that we have refeuled.
pq is a priority queue that we store all available gas.

We initial res = 0 and in every loop:

We add all reachable stop to priority queue.
We pop out the largest gas from pq and refeul once.
If we can't refuel, means that we can not go forward and return -1

    public int minRefuelStops(int target, int cur, int[][] s) {
        Queue<Integer> pq = new PriorityQueue<>();
        int i = 0, res;
        for (res = 0; cur < target; res++) {
            while (i < s.length && s[i][0] <= cur)
                pq.offer(-s[i++][1]);
            if (pq.isEmpty()) return -1;
            cur += -pq.poll();
        }
        return res;
    }

https://leetcode.com/articles/minimum-number-of-refueling-stops/
When driving past a gas station, let's remember the amount of fuel it contained. We don't need to decide yet whether to fuel up here or not - for example, there could be a bigger gas station up ahead that we would rather refuel at.

When we run out of fuel before reaching the next station, we'll retroactively fuel up: greedily choosing the largest gas stations first.

This is guaranteed to succeed because we drive the largest distance possible before each refueling stop, and therefore have the largest choice of gas stations to (retroactively) stop at.

pq ("priority queue") will be a max-heap of the capacity of each gas station we've driven by. We'll also keep track of tank, our current fuel.

When we reach a station but have negative fuel (ie. we needed to have refueled at some point in the past), we will add the capacities of the largest gas stations we've driven by until the fuel is non-negative.

If at any point this process fails (that is, no more gas stations), then the task is impossible.

public int minRefuelStops(int target, int tank, int[][] stations) {

// pq is a maxheap of gas station capacities

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

int ans = 0, prev = 0;

for (int[] station : stations) {

int location = station[0];

int capacity = station[1];

tank -= location - prev;

while (!pq.isEmpty() && tank < 0) { // must refuel in past

tank += pq.poll();

ans++;

}

if (tank < 0)

return -1;

pq.offer(capacity);

prev = location;

}

// Repeat body for station = (target, inf)

{

tank -= target - prev;

while (!pq.isEmpty() && tank < 0) {

tank += pq.poll();

ans++;

}

if (tank < 0)

return -1;

}

return ans;

}

X. DP
https://blog.csdn.net/XX_123_1_RJ/article/details/81206386
这个题目使用动态规划的思想，基本思路，设dp[i]表示第i次加油之后可以达到的最远距离，很显然，i <= 加油站的个数，求出dp之后，从头遍历一边，找到第一个 dp[i] >= target 的 i ，就是最少的加油次数，如果没有就返回-1。
（1）问题 dp[i] 怎么求？首先，从头开遍历加油站，每当遍历到第i个加油站时，dp[t+1] = max(dp[t+1], dp[t] + arr[i])，其中t+1 <= i，然后依次，从后向前更新dp，可以这样理解，dp[t] 再加一次油arr[i]，得到的新的dp[t+1]是否是比之前的dp[t+1]大？如果大就更新。依次遍历递推，直至结束。值得思考是的，仔细观察递推公式：dp[t+1] = max(dp[t+1], dp[t] + arr[i])你会发现，无论更新与否，dp[t+1] 始终代表的是第 t+1 次加油。
https://leetcode.com/articles/minimum-number-of-refueling-stops/
Time Complexity:

O(N^2)

, where

N

is the length of stations.

Let's determine dp[i], the farthest location we can get to using i refueling stops. This is motivated by the fact that we want the smallest i for which dp[i] >= target.

Algorithm

Let's update dp as we consider each station in order. With no stations, clearly we can get a maximum distance of startFuel with 0 refueling stops.

Now let's look at the update step. When adding a station station[i] = (location, capacity), any time we could reach this station with t refueling stops, we can now reach capacity further with t+1refueling stops.

For example, if we could reach a distance of 15 with 1 refueling stop, and now we added a station at location 10 with 30 liters of fuel, then we could potentially reach a distance of 45 with 2 refueling stops.

public int minRefuelStops(int target, int startFuel, int[][] stations) {

int N = stations.length;

long[] dp = new long[N + 1];

dp[0] = startFuel;

for (int i = 0; i < N; ++i)

for (int t = i; t >= 0; --t)

if (dp[t] >= stations[i][0])

dp[t + 1] = Math.max(dp[t + 1], dp[t] + (long) stations[i][1]);

for (int i = 0; i <= N; ++i)

if (dp[i] >= target)

return i;

return -1;

}

https://leetcode.com/problems/minimum-number-of-refueling-stops/discuss/151850/C%2B%2B-DP-solution-Space-complexity-from-O(n2)-to-O(n).

Denote by dp[i][j] the farthest location we can get to using exactly j refueling stops among the first i refueling stops, for j <= i.

Initially dp[i][0] = startFuel, for i = 0, ..., n.

dp[][] is updated as follows. For the gas station i, one can either refuel the car at this station if dp[i-1][j-1] >= stations[i][0], and dp[i][j] = max(dp[i][j], dp[i-1][j-1] + stations[i][1]). Or one can choose to not refuel the car, and dp[i][j] = max(dp[i][j], dp[i-1][j]) if j <= i-1.

Here is the code for O(n^2) space complexity dynamic programming.

for (int i = 0; i <= n; i++) dp[i][0] = startFuel;

for (int i = 0; i < n; i++)
 for (int j = 0; j <= i; j++) {
  if (i >= j+1)
   dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1]);
  if (dp[i][j] >= stations[i][0])
   dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + stations[i][1]);
 }

It is worth pointing out that the (i+1)-th raws depends only on the values on the i-th raws. Hence, we can reduce the space complexity.
The previous code is equivalent to

dp[0] = startFuel;
for (int i = 0; i < n; i++)
 for (int j = i; j >= 0; j--) {
  if (dp[j] >= stations[i][0])
   dp[j+1] = max(dp[j+1], dp[j] + stations[i][1]);
 }

https://leetcode.com/problems/minimum-number-of-refueling-stops/discuss/149839/DP-O(N2)-and-Priority-Queue-O(NlogN)

dp[t] means the furthest distance that we can get with t times of refueling.

So for every station s[i],
if the current distance dp[t] >= s[i][0], we can refuel:
dp[t + 1] = max(dp[t + 1], dp[t] + s[i][1])

In the end, we'll return the first t with dp[i] >= target,
otherwise we'll return -1.

    public int minRefuelStops(int target, int startFuel, int[][] s) {
        long[] dp = new long[s.length + 1];
        dp[0] = startFuel;
        for (int i = 0; i < s.length; ++i)
            for (int t = i; t >= 0 && dp[t] >= s[i][0]; --t)
                dp[t + 1] = Math.max(dp[t + 1], dp[t] + s[i][1]);
        for (int t = 0; t <= s.length; ++t)
            if (dp[t] >= target) return t;
        return -1;
    }

LeetCode 871 - Minimum Number of Refueling Stops

Labels

Popular Posts