LeetCode 853. Car Fleet

853. Car Fleet

解法

由于给的位置是没有规律的，并且给的N的范围是10^4，因此第一时间想到排序。
继续分析，两辆车在直线上运行时，距离终点更近的车的到达时间不会被远车影响，因此我们可以考虑从后往前考虑车的到达情况。
从后往前，先计算当前车的到达时间，如果后面的车的到达时间比当前车短，则两者相遇，车队数目减一，到达时间不变。如果后面的车的到达时间长，则两者不相遇，车队数目不变。

代码

class Solution {
public:
    typedef pair<int, int> PII;
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        vector<PII> data;
        for (int i = 0; i < n; i ++) {
            data.push_back({position[i], speed[i]});
        }
        sort(data.begin(), data.end());
        int ans = n;
        double time = 0, eps = 1e-6;
        for (int i = n - 1; i >= 0; i --) {
            // cout << i << endl;
            double tmp = (target - data[i].first) / (double)data[i].second;
            if (tmp > time + eps) {
                time = tmp;
            } else {
                ans --;
            }
        }
        return ans;
    }
};