871. Minimum Number of Refueling Stops

Came up with BFS solution first time, but TLE
We need to compress the state

Version #3 Knapsack[TODO]
我自己intuitive的想法
写得太复杂了，回头再写

Version #2 Neat PriorityQueue Version
我自己的答案是遍历stations，写得很长，因为所有stations走完并不是终点，还需要继续从heap里面pop去看能否到达target
这个答案是discuss里面的，完全换了一个角度
for循环的停止条件就是furthest到达了target才停止
步进条件就是每一次都尽可能地走远，走到没得走为止
如果不能走就pop出油最多的station加油
完美地把我之前答案的两个Part揉在一起了

65.76 % 
class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int furthest = startFuel;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int result = 0;
        int i = 0;
        for (result = 0; furthest < target; result++) {
            while (i < stations.length && furthest >= stations[i][0]) {
                maxHeap.offer(stations[i][1]);
                i++;
            }
            if (maxHeap.isEmpty()) {
                return -1;
            }
            furthest += maxHeap.poll();
        }
        return result;
    }
}

Version #1 Greedy with PriorityQueue

87.16 %
class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int furthest = startFuel;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int result = 0;
        for (int[] station : stations) {
            if (furthest >= target) {
                return result;
            }
            while (!maxHeap.isEmpty() && furthest < station[0]) {
                furthest += maxHeap.poll();
                result++;
            }
            if (furthest < station[0]) {
                return -1;
            }
            maxHeap.offer(station[1]);
        }
        while (!maxHeap.isEmpty() && furthest < target) {
            furthest += maxHeap.poll();
            result++;
        }
        return furthest >= target ? result : -1;
    }
}