จำนวนการเติมน้ำมันน้อยที่สุดใน C++

คำอธิบายปัญหา

รถเดินทาง target ไมล์ เริ่มต้นน้ำมัน startFuel ใช้น้ำมัน 1 ลิตร/ไมล์ มีสถานีน้ำมัน st[i] = [position, fuel] หาจุดหยุดเติมน้อยที่สุดเพื่อถึงจุดหมาย หากไม่ได้คืน -1

ตัวอย่าง

target=100, startFuel=10, stations=[[10,40],[20,30],[30,20],[60,40]] → Output: 3

แนวทางแก้ปัญหา: Greedy + Max Heap

1. ขับต่อไปเรื่อยๆ จนน้ำมันหมด
2. ตอนน้ำมันจะหมด ให้ถอยหลัง "เลือก" สถานีที่ผ่านมาที่ให้น้ำมันมากที่สุด (max heap)
3. นี่คือ greedy: เลือกสถานีที่ให้ fuel มากที่สุดจากสถานีที่ผ่านมาแล้ว

อัลกอริทึม

• curr = startFuel, i = 0 (index สถานี), cnt = 0
• while curr < target:
  • เพิ่มสถานีที่ position ≤ curr เข้า max heap
  • ถ้า heap ว่าง → return -1
  • curr += heap.top(); heap.pop(); cnt++
• return cnt

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minRefuelStops(int target, int fuel, vector<vector<int>>& st) {
        sort(st.begin(), st.end());
        priority_queue<int> pq;
        int i = 0, cnt = 0, curr = fuel;
        
        while(curr < target) {
            while(i < st.size() && st[i][0] <= curr) {
                pq.push(st[i][1]);
                i++;
            }
            if(pq.empty()) return -1;
            curr += pq.top(); pq.pop();
            cnt++;
        }
        return cnt;
    }
};

ความซับซ้อน

• เวลา: O(n log n) (sort + heap operations)
• พื้นที่: O(n)