# 0871. Minimum Number of Refueling Stops
###### tags: `Leetcode` `Hard` `Greedy` `Priority Queue`
Link: https://leetcode.com/problems/minimum-number-of-refueling-stops/description/
## 思路
我们可以这样考虑．现在有一定量的```startFuel```，假设可以驶过两个加油站，但是达不到第三个加油站．说明我们应该在前两个加油站中的某一个或全部两个停下来加油．但是该加多少呢？

其实，我们不用想的太远，千里之行始于足下，目前只需要加油使得能够开到第三个加油站即可．于是，我们优先考虑前两个加油站里较多的那一个，不够的话就算上另一个．反正到了第三个加油站后，我们就又多了一个option．等过了第三个加油站，我们再类似地考虑，是否需要加油才能开到第四个加油站．如果需要，就在前三个加油站里面尚未加过油的那些里，选择油量最多的那个即可；不需要的话，就把第四个加油站放入option list,考虑是否需要加油才能开到第五个加油站...

这就是贪心法的最优策略．特别注意，我们得把```target```当做一个加油站来处理。不能只用贪心法处理到最后一个加油站，再用剩下的```curFuel```来考虑是否能到```target```，那样是错误的：因为这样的话你只是用尽全力到达最后一个加油站，而并没有用尽全力去到达```target```。
## Code

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        if(startFuel>=target) return 0;
        int n = stations.length;
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int curr = startFuel;
        int cnt = 0;
        for(int i=0; i<=n; i++){
            int pos, fuel;
            if(i==n){
                pos = target;
                fuel = 0;
            }
            else{
                pos = stations[i][0];
                fuel = stations[i][1];
            }
            if(curr>=pos){
                pq.add(fuel);
            }
            else{
                while(curr<pos && !pq.isEmpty()){
                    curr+=pq.poll();
                    cnt++;
                }
                if(curr<pos) return -1;
                pq.add(fuel);
            }
        }
        return cnt;
    }
}