LeetCode 0871. Minimum refueling times - similar to poj2431 jungle adventure

【LetMeFly】871. Minimum refueling times - Be similar to POJ2431 Jungle exploration

Force button topic link ：https://leetcode.cn/problems/minimum-number-of-refueling-stops/

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

Method 1 ： greedy + Priority queue

This problem makes it easy to think of recursion .

This problem can be solved by reference Jungle exploration

And it's very simple :

If there are multiple gas stations within the available distance , Then join the refueling volume of these refueling stations （ Priority queue ）.

If you walk to the next gas station, the oil will run out , You need to refuel （ The largest refueling volume in the priority queue ） Keep walking after .

When the fuel volume is greater than or equal to the distance from the truck to the town L End of time .

• Time complexity $O(n\log n)$, among $n$ It's the number of gas stations
• Spatial complexity $O(n)$

AC Code

C++

class Solution {
    
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
    
        sort(stations.begin(), stations.end(), [](vector<int>& a, vector<int>& b) {
    
            return a[0] < b[0];
        });
        int ans = 0;
        int canGo = startFuel;
        int loc = 0;
        priority_queue<int> pq;
        while (canGo < target) {
    
            while (loc < stations.size() && stations[loc][0] <= canGo) {
    
                pq.push(stations[loc][1]);
                loc++;
            }
            if (pq.empty())
                return -1;
            canGo += pq.top();
            pq.pop();
            ans++;
        }
        return ans;
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125575683