Số trạm xăng dừng tối thiểu trong C++

Xe đi từ 0 đến target dặm, bình xăng vô hạn, ban đầu có startFuel lít (1 lít/dặm). Trạm xăng tại station[i][0] dặm, có station[i][1] lít. Tìm số lần dừng tải xăng tối thiểu để đến đích. Không thể thì -1.

Ví dụ: target=100, startFuel=10, stations=[[10,40],[20,30],[30,20],[60,40]] → 3.

Giải thuật

1. Sắp xếp trạm theo vị trí.
2. Dùng max-heap lưu lượng xăng các trạm đã qua.
3. curr = startFuel. Khi curr < target:
   • Thêm tất cả trạm tại vị trí ≤ curr vào heap.
   • Nếu heap rỗng → -1.
   • Lấy top heap (trạm nhiều xăng nhất), curr += top, đếm++.
4. Trả về đếm.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minRefuelStops(int target, int fuel, vector<vector<int>> &st) {
        int curr = 0;
        sort(st.begin(), st.end());
        priority_queue<int> pq;
        int i = 0, cnt = 0;
        curr += fuel;
        while (curr < target) {
            cnt++;
            while (i < st.size() && st[i][0] <= curr) {
                pq.push(st[i][1]);
                i++;
            }
            if (pq.empty()) break;
            curr += pq.top();
            pq.pop();
        }
        return curr >= target ? cnt : -1;
    }
};
int main(){
    Solution ob;
    vector<vector<int>> v = {{10,40},{20,30},{30,20},{60,40}};
    cout << (ob.minRefuelStops(100, 10, v));
}

Đầu vào

100, 10, {{10,40},{20,30},{30,20},{60,40}}

Đầu ra

3