871. Minimum refueling times

Original link :871. Minimum refueling times

 

solution:

        This topic examines the priority queue + greedy . The meaning of the title is equivalent to carrying all the gasoline on your body during driving , If the car cannot reach the next gas station, add the barrel with the most gasoline , Finally, count the number of refueling .

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        if(stations.size() == 0) {  // There is no gas station , Whether it can arrive depends only on the initial oil volume 
            if(startFuel >= target) return 0;
            else return -1;
        }

        priority_queue<int,vector<int>,less<int>> heap; // Define a large root heap 
        int miles = startFuel;  // The distance you can reach 
        int res = 0;// Refueling times 
        for(int i = 0;i < stations.size();i++) {
            if(miles >= target) return res;  // You can reach and jump out of the loop 
            while(miles < stations[i][0]) {    // When the mileage is not enough to reach the next gas station 
                if(heap.empty()) return -1; // There is no gasoline to add , Can't arrive 
                auto oil = heap.top();
                heap.pop();
                miles += oil;
                res++;
            }
            heap.push(stations[i][1]);
        }
        // I have brought all the gasoline , But we haven't reached the finish line for special judgment 
        while(miles < target) {
            if(heap.empty()) return -1;
            auto oil = heap.top();
            heap.pop();
            miles += oil;
            res++;
        }
        return res;
    }
};