871. Minimum refueling times: simple priority queue (heap) greedy question

Title Description

This is a LeetCode Upper 871. Minimum refueling times , The difficulty is difficult .

Tag : 「 greedy 」、「 Priority queue （ Pile up ）」、「 simulation 」

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 Miles will be used 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 .

Be careful ： If the remaining fuel when the car arrives at the gas station is , It can still refuel there . If the remaining fuel is , 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 ：

greedy + Priority queue （ Pile up ）

For convenience , We remember target by t, remember startFuel by start, remember stations by ss.

We can simulate the progress , Use n Represents the total number of gas stations ,idx Represents the subscript of the passing gas station , Use remain Represents how much oil there is currently （ Starting with remain = start),loc Represents how far we have gone ,ans For the answer （ At least the number of times you need to refuel ）.

as long as loc < t, The representative hasn't arrived yet （ after ） Target location , We can continue to simulate the progress , Each time will be remain Add up to loc in , It means to use up the remaining oil , The farthest you can go , At the same time, the location ss[idx][0] <= loc The number of gas stations added to the priority queue （ Big root pile , Reverse the order according to the oil quantity ） in , Check again whether loc < t（ Next cycle ）, At this time, due to emptying the remaining oil remain, We try from the priority queue （ Big root pile ） Take out the gas station with the largest fuel volume in the past and refuel （ At the same time, the number of refueling ans Add one operation ）, Use new remaining oil remain Repeat the process , Until you meet loc >= t Or no oil to add .

It is easy to prove the correctness of this practice ： It also consumes one refueling time , Always choose the gas station with the largest fuel volume to refuel , It can ensure that there is no better result .

Code ：

class Solution {
    public int minRefuelStops(int t, int start, int[][] ss) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int n = ss.length, idx = 0;
        int remain = start, loc = 0, ans = 0;
        while (loc < t) {
            if (remain == 0) {
                if (!q.isEmpty() && ++ans >= 0) remain += q.poll();
                else return -1;
            }
            loc += remain; remain = 0;
            while (idx < n && ss[idx][0] <= loc) q.add(ss[idx++][1]);
        }
        return ans;
    }
}

• Time complexity ：
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series No.871 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .