871. Minimum Number of Refueling Stops

這題有關於用dp O(n²)的方法我一直看不太明白

反倒是proirity_queue的方式還比較好懂

題目的意思是, 有一台車要到目的地, 途中會經過幾間加油站, 我們如何用最少的加油次數就能到加油站

我們就從0次開始看, 假設不加油, 我最遠可以到哪邊, 然後途中經過的加油站我們都把他加到proirity_queue, 等這一run結束後, 假設已經到終點了我們就退出迴圈, 還沒到的話, 我們就從途中經過的加油站, 找一間可以加最多油的幫忙加到現在的油箱, 倘若已經都找完, 表示還沒到加油站前或目的地前,已經沒油了

每次從push加油站進pq裡的時間複雜度為O(nlogn).

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int i = 0;
        int res = 0;
        priority_queue<int> pq;
        int cur = startFuel;
        for(res = 0; cur < target;res++){
            while(i < stations.size() && stations[i][0] <= cur){
                pq.push(stations[i][1]);
                i++;
            }
            if(pq.empty()) return -1;
            cur += pq.top();
            pq.pop();
        }
        return res;
    }
};