871. Minimum Number of Refueling Stops

subject ：

A car travels from a starting position to a destination which is target miles east of the starting position.

There are gas stations along the way. The gas stations are represented as an array stations where stations[i] = [positioni, fueli] indicates that the ith gas station is positioni miles east of the starting position and has fueli liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses one liter of gas per one 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.

Return the minimum 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 not 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.

Constraints:

• 1 <= target, startFuel <= 109
• 0 <= stations.length <= 500
• 0 <= positioni <= positioni+1 < target
• 1 <= fueli < 109

Ideas 1：

The first reaction is to do it with recursion ,f[i][j] It means that after the second i After a gas station , come on. j The maximum distance that can be reached , Finally, you only need to find the smallest j also f[i][j] Greater than or equal to target that will do . In the state transition equation f[i][j] You can come from three places ：1)f[i][j - 1], The representative passed the current station , But don't refuel at the current station ;2)f[i - 1][j], It means reaching the i - 1 That is, the previous station , And added j Secondary oil , That is, there was no refueling at the last station ;3)f[i - 1][j - 1] + stations[i - 1][1], That is, after the i - 1 A station , And added oil at the last station , Of course, the condition here is f[i - 1][j - 1] The maximum distance of must be greater than stations[i - 1][0] Big , Otherwise, you can't get to the last station . Initialization we use n = stations.size() + 1, namely f[i][j] When j be equal to 0 It means f[i][0] All of them have not been oiled , Then their value should be startFuel, as for f[0][j], No initialization required , because j It must be less than waiting i, That is, you can't refuel more than the passing station .

Code 1:

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int n = stations.size() + 1;
        vector<vector<long>> f(n, vector<long>(n));
        for (int i = 0; i < n; i++) {
            f[i][0] = startFuel;
        }      
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= i; j++) {
                if (f[i - 1][j - 1] >= stations[i - 1][0]) {
                    f[i][j] = f[i - 1][j - 1] + stations[i - 1][1];
                }
                f[i][j] = max({f[i - 1][j], f[i][j - 1], f[i][j]});
            }
        }
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {
                if (f[i][j] >= target)
                    return j;
            }
        }
        return -1;
    }
};

Ideas 2：

In essence , The problem requires that we need to add the most oil in the minimum number of refueling , That is, add the most oil you can every time you refuel . But every time we pass the station , In fact, only the current station can choose , So how to form options ？ The answer is not to refuel every time you pass the station , Record the fuel that can be added into a priority queue , When we need to refuel, we can take it out and refuel for ourselves . The priority queue here is to manage the maximum , What we can take out at any time is the most oil . First of all, the maximum distance we can reach dist Namely startFuel, After judgment dist and target, once dist Greater than or equal to target It's over . In circulation , Every time we pass the station , If at present dist Be able to reach the station , Then let's not refuel , Instead, add oil to the priority queue ; If you can't reach the station , Then come on , If the priority queue has run out of oil , Prove that we can't reach target, Go straight back to -1; If the priority queue has oil , Then take out the biggest oil , give dist, At the same time, update the refueling times .

Code 2：

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        priority_queue<int> q;
        int dist = startFuel, count = 0;
        int i = 0;
        while (dist < target) {
            if (i < stations.size() && dist >= stations[i][0]) {  // Being able to get to the station means that the oil is enough for the time being
                q.push(stations[i][1]);  // Don't refuel first , Save up
                i++;
            } else {
                if (q.size()) {  // There is oil to add
                    dist += q.top();    // come on.
                    q.pop();
                    count++;  // Number of updates
                } else {  // No oil to add , Cannot reach target
                    return -1;
                }
            }
        }
        return count;
    }
};