LeetCode 871. Minimum refueling times

The car set off from the starting point to the destination , The purpose is to the east of the starting position target  Miles away .

There are gas stations along the way , Every  station[i]  For a gas station , It's east of the starting point  station[i][0]  Miles away , And there are  station[i][1]  A litre of petrol .

Suppose the capacity of the car's fuel tank is infinite , At first there was  startFuel  Liter fuel . Every time it drives 1 Miles will be used 1 A litre of petrol .

When the car arrives at the gas station , It may stop to refuel , Transfer all gasoline from the gas station to the car .

In order to reach the destination , What's the minimum number of refuels necessary for a car ？ If you can't get to your destination , Then return to -1 .

Be careful ： If the remaining fuel when the car arrives at the gas station is 0, It can still refuel there . If the remaining fuel is 0, Still think it has reached its destination .

Example 1：

 Input ：target = 1, startFuel = 1, stations = []
 Output ：0
 explain ： We can get to our destination without refueling .

Example 2：

 Input ：target = 100, startFuel = 1, stations = [[10,100]]
 Output ：-1
 explain ： We can't get to our destination , Not even getting to the first gas station .

Example 3：

 Input ：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
 Output ：2
 explain ：
 We set out with  10  Liter fuel .
 We drove to the starting point  10  The gas station at mile , Consume  10  Liter fuel . Take the gas from  0  To add to  60  l .
 then , We from  10  The gas station is miles away  60  The gas station at mile （ Consume  50  Liter fuel ）,
 And take the gas from  10  To add to  50  l . Then we drove to our destination .
 We are on the way 1 Two gas stations stop , So back  2 .

 

Tips ：

1. 1 <= target, startFuel, stations[i][1] <= 10^9
2. 0 <= stations.length <= 500
3. 0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

Related labels

greedy Array Dynamic programming Pile up （ Priority queue ）

Greedy question , It's difficult to prove , But the idea is more direct .

The specific methods are as follows .

1. Calculate the current position （ Gas station or destination ） The distance from the previous position , According to the distance difference, the amount of gasoline needed to drive from the previous position to the current position , Subtract the amount of gasoline used from the remaining amount of gasoline .

2. If the remaining gasoline quantity is less than $0$, It means that you cannot drive from the previous position to the current position without refueling , We need to refuel . Take the largest element in the priority queue and add it to the remaining gasoline , And increase the refueling times $1$, Repeat this operation until the remaining gasoline quantity is greater than or equal to $0$ Or the priority queue becomes empty .

3. If the priority queue becomes empty , The remaining amount of gasoline is still less than $0$, It means that you still can't reach the current position after refueling at all the passing gas stations , return $-1$.

4. If the current location is a gas station , Then add the refueling volume of the current gas station to the priority queue , And update the previous location with the current location .

class Solution {
    
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
    
        stations.push_back({
    target,0});
        int res=0;
        priority_queue<int> heap;
        for (auto& p:stations) {
    
            int x=p[0],y=p[1];
            while(heap.size() && startFuel<x) {
    
                startFuel += heap.top();
                heap.pop();
                res ++;
            }
            if (startFuel<x) return -1;
            heap.push(y);
        }
        return res;
    }
};