853. Car Fleet

解題思路

第一步是想要怎麼找出最後速度會相等的車？速度最後會相等，代表出發位置靠後的車會趕上前面的車，也表示靠後的車原本到達目的地的時間會比較短。

時間的計算則是 (目的地位置 - 出發位置) / 車速。

又因為兩車相遇後，快車速度變慢，所以用stack紀錄有哪些車，而快車就不放進去。最後stack長度即為解。

程式碼

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        vector<pair<int, int>> cars;
        for(int i=0; i<position.size(); i++)
            cars.push_back(make_pair(position[i], speed[i]));
        sort(cars.begin(), cars.end());

        stack<pair<int, int>> st;
        st.push(cars.back());
        double currentTime = (target - cars.back().first) / (double)cars.back().second;
        for(int i=cars.size() - 2; i>=0; i--)
        {
            if((target - cars[i].first)/(double)cars[i].second > currentTime)
            {
                st.push(cars[i]);
                currentTime = (target - cars[i].first)/(double)cars[i].second;
            }
        }
        return st.size();
    }
};