กลุ่มรถ (Car Fleet) ใน C++

มีรถ N คันเดินทางไปจุดหมายระยะ target ไมล์ รถแต่ละคันมีตำแหน่งเริ่มต้น position[i] และความเร็ว speed[i] รถไม่สามารถแซงกันได้ จะขับติดกันเป็นฝูง (fleet) หาจำนวน fleet ที่ถึงจุดหมาย

ตัวอย่าง

Input − target=12, pos=[10,8,0,5,3], speed=[2,4,1,1,3] Output − 3

คำอธิบาย − รถที่ 10 และ 8 รวมเป็น fleet ที่ 12, รถที่ 0 เดินคนเดียว, รถที่ 5 และ 3 รวมเป็น fleet ที่ 6

แนวทางการแก้ปัญหา

• จับคู่ (position, speed) เรียงตามตำแหน่งจากใกล้จุดหมายไปไกล
• คำนวณเวลาที่แต่ละรถใช้ถึงจุดหมาย: (target - pos) / speed
• ใช้ stack: ถ้ารถถัดไปใช้เวลา ≤ รถหน้า (เร็วกว่าหรือเท่ากัน) จะรวมเป็น fleet เดียวกัน (pop stack)
• จำนวน fleet = ขนาด stack สุดท้าย

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

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

class Solution {
public:
    int carFleet(int target, vector& pos, vector& speed) {
        vector> cars;
        int n = pos.size();
        for (int i = 0; i < n; i++)
            cars.push_back({pos[i], speed[i]});
        
        sort(cars.begin(), cars.end());
        stack st;
        
        for (int i = n - 1; i >= 0; i--) {
            double time = (target - cars[i].first) / cars[i].second;
            if (st.empty() || time > st.top())
                st.push(time);
        }
        return st.size();
    }
};

int main() {
    vector pos = {10, 8, 0, 5, 3};
    vector speed = {2, 4, 1, 1, 3};
    Solution ob;
    cout << ob.carFleet(12, pos, speed); // 3
    return 0;
}

ผลลัพธ์

3