Leetcode-871: minimum refueling times

subject

Topic linking

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 .

Problem solving

Method 1 ： greedy

Reference link

This solution and leetcode-45： Jumping game II It's similar , Calculate the maximum coverage distance each time . How many times can you cover the end , It means several times .

class Solution {
    
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
    
        priority_queue<int> q;
        int res=0;
        int i=0;
        while(startFuel<target){
    
            while(i<stations.size()&&startFuel>=stations[i][0]){
    
                q.push(stations[i++][1]);
            }
            if(q.empty()) return -1;
            startFuel+=q.top();
            q.pop();
            res++;
        }
        return res;
    }
};