Đoàn xe (Car Fleet) C++

N xe chạy về đích target dặm. Xe i tại position[i] với tốc độ speed[i]. Xe không thể vượt, chỉ có thể đuổi kịp và chạy cùng tốc độ (thành fleet). Đếm số fleet đến đích.

Ví dụ

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

Giải thích - Fleet 1: xe 10,8 gặp nhau tại 12. Fleet 2: xe 0 đơn độc. Fleet 3: xe 5,3 gặp nhau tại 6.

Phương pháp tiếp cận

• Tạo vector cặp (position, speed), sắp xếp theo position
• Tính thời gian đến đích: time = (target - pos) / speed
• Duyệt từ xe gần đích nhất, dùng stack lưu thời gian fleet
• Nếu time hiện tại ≤ top stack → cùng fleet (pop stack, giảm count)
• Push time hiện tại vào stack

Ví dụ code C++

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

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        vector<pair<double, double>> v;
        int n = position.size();
        for (int i = 0; i < n; i++)
            v.push_back({position[i], speed[i]});

        int ret = n;
        sort(v.begin(), v.end());
        stack<double> st;

        for (int i = 0; i < n; i++) {
            double time = (target - v[i].first) / v[i].second;
            while (!st.empty() && st.top() <= time) {
                ret--;
                st.pop();
            }
            st.push(time);
        }
        return ret;
    }
};

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

Kết quả

3