526互联

871.minimum number of refueling stops

发布时间 2023-07-26 16:04:21作者: zwyyy456

Description

871.minimum-number-of-refueling-stops

Solution

Dynamic programming

In this problem, the number is finite, and there is a recurrence relation, so we can use dynamic programming to solve this problem.

Let dp[i][j] means the furthest distance we can reach after passing throught i stations and adding fuel for j times. Obviously, i >= j.

So we can discuss dp[i][j] in two cases:

  • We don't add fuel at the ith station: dp[i][j] = dp[i - 1][j]
  • We add fuel in the ith station(We have to arrive at the ith station in the case we have just added fuel for j - 1 times before, that is: dp[i - 1][j - 1] >= stations[i - 1][0]): dp[i][j] = dp[i - 1][j - 1] + stations[i - 1][1].

dp[i][j] is the maximum value of the two values.

Greedy algorithm

It is easy to see that the optimal strategy is to add fuel in the station with the most fuel. Actually, we can get fuel from the station that we passed through. For each time we can't get to the next station or destination, we get fuel from the station with the most fuel that we passed through but didn't get fuel from, until we get to the next station or destination or there is no station we can get fuel from.

Code

Dynamic programming

class Solution {
  public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>> &stations) {
        int n = stations.size();
        if (n == 0) {
            if (startFuel >= target)
                return 0;
            return -1;
        }
        vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
        dp[0][0] = startFuel;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = stations[i - 1][0] <= startFuel ? startFuel : 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // We have to arrive at the `i`th station in the case we have just added fuel for `j - 1` times before,
                if (dp[i - 1][j - 1] >= stations[i - 1][0])
                    dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1]);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        int res = 600;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (dp[i][j] >= target)
                    res = std::min(res, j);
            }
        }
        return res >= 600 ? -1 : res;
    }
};

Greedy algorithm

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int n = stations.size();
        if (n == 0) {
            if (startFuel >= target)
                return 0;
            return -1;
        }
        if (startFuel < stations[0][0])
            return -1;
        int res = 0;
        auto cmp = [&](vector<int> &v1, vector<int> &v2){
            return v1[1] <= v2[1];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp); // heap top is the station with the most fuel
        pq.push(stations[0]);
        int cur_fuel = startFuel - stations[0][0];
        for (int i = 1; i < n; i++) {
            while (!pq.empty() && cur_fuel < stations[i][0] - stations[i - 1][0]) { // notice the **while**, and judge if pq is empty first!
                cur_fuel += pq.top()[1];
                pq.pop();
                res++;
            }
            if (cur_fuel < stations[i][0] - stations[i - 1][0]) {
                return -1;
            }
            pq.push(stations[i]);
            cur_fuel = cur_fuel - (stations[i][0] - stations[i - 1][0]);
        }
        while (!pq.empty() && cur_fuel < target - stations[n - 1][0]) {
            cur_fuel += pq.top()[1];
            res++;
            pq.pop();
        }
        if (cur_fuel < target - stations[n - 1][0])
            return -1;
        return res;
    }
};