871. Minimum Number of Refueling Stops

T: O(nlogn), n is stations size

S: O(n)

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int[][] gasStations = new int[stations.length+1][2];
        for (int i = 0; i < stations.length; i++) {
            gasStations[i] = stations[i];
        }
        //treat target as last station
        gasStations[gasStations.length-1] = new int[]{target, 0};  // 
        
        Queue<Integer> pq = new PriorityQueue<>((a, b) -> b-a);
        
        int curFuel = startFuel;
        int idx = 0;
        int count = 0;

        while (idx < gasStations.length) { // iterate all stations
            
            // indicates that the ith gas station‘s positioni miles east of the starting position 
            // gasStations[idx][0] 是距離起點的距離(可以當成是位置座標)
            int dist = gasStations[idx][0];
            int gas = gasStations[idx][1];
            
            // 所以只要確保 curFuel 都夠到這個點就好
            if (curFuel >= dist) {
                pq.offer(gas);
                idx++;
            } else {
                
                // 不夠到下一站時, keep adding gas
                while (!pq.isEmpty() && curFuel < dist) {  
                    curFuel += pq.poll(); 
                    count++; 
                }
                
                if (pq.isEmpty() && curFuel < dist) {
                    return -1;
                }
            }
            
        }
        return count;
    }
}

/*
It uses one liter of gas per one mile that it drives.

Return the "minimum number" of refueling stops the car must make in order to reach its destination. 
If it cannot reach the destination, return -1.


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

60       40
10 20 30 60 100

so if curFuel can support util one station, it works.

1.
treat target as last station [target, 0]

2.
when we can arrive a station, but don't need add gas, just save the gas in pq this time

3.
in the later, if we found we shoud add gas, then pop the max gas from pq (count++)

4.
if pq is empty and we cant arrive next station, return -1

because gasStations[idx][0] 是一個絕對距離 （距離起點
indicates that the ith gas station‘s positioni miles east of the starting position 


T: O(nlogn), n is stations size
S: O(n)

*/