LeetCode 871. Minimum refueling times

871. Minimum refueling times

 

 【 greedy + Priority queue 】 Add all the gas stations that can reach the current fuel volume to the priority queue , Sort according to the refueling volume , If you can't reach the destination at present , Just add the largest oil in the queue , Then continue to join the queue of gas stations that can arrive after filling up , If the last queue is empty, it will return before reaching the end -1.

Take an example 3 by ：

target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] 

1. At first there was 10, Only [10, 60], Add him to the queue . 

2. At present, it only drives to 10, Not yet 100, Therefore, we need to refuel halfway , Put... In the queue 60 Take it out and refuel , You can drive to 70, So put the back 70 Previous gas stations have joined the queue , And according to the oil quantity, it is ：[60, 40], [20, 30], [30, 30]

3. Currently driving 70, Need to continue to refuel , Get the largest in the queue 40, The total mileage after adding is 110 You can reach the end .

The essence of greed lies in , Choose the gas station with high fuel volume as far as possible among the gas stations that can reach the current fuel volume .

class Solution {

    //  greedy   Find the gas station that can be reached with the most 

    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int sum = startFuel;
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((a, b) -> { return b[1] - a[1]; });
        int i = 0, n = stations.length, ans = 0;
        while (true) {
            if (sum >= target) {
                return ans;
            }
            for (; i < n; i++) {
                if (stations[i][0] <= sum) {
                    queue.offer(stations[i]);
                } else {
                    break;
                }
            }
            if (queue.isEmpty()) {
                return -1;
            }
            int[] top = queue.poll();
            sum += top[1];
            ans++;
        }
    }
}