LeetCode 1094 Car Pooling

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-02-12 17:08:27
    编辑于：2022-02-12 17:21:47
    浏览量：941

概述

https://leetcode.com/problems/car-pooling/

暴力法

维护一个里程数组，里面记录对应该 km 的汽车容量，如果末段容量降到了负数，则拼车失败。

时间复杂度 O(mn)，空间复杂度 O(n)，其中 m 为拼车人数，n 为距离。

差分数组

显然我们应该对范围进行操作。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1001, 0);
        int maxD = INT_MIN;
        int minD = INT_MAX;
        for (auto& t : trips) {
            diff[t[2]] += t[0];
            diff[t[1]] -= t[0];
            maxD = max(maxD, t[2]);
            minD = min(minD, t[1]);
        }
        int sum = 0;
        for (int i = maxD; i >= minD; i --) {
            int rest = capacity - diff[i] - sum;
            if (rest < 0) return false;
            sum += diff[i];
        }
        return true;
    }
};

有个可以优化的地方就是，实际上我们不需要遍历整个路段，只需要逆序遍历有人上下车的点即可。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        unordered_map<int, int> diff;
        set<int> s;
        for (auto& t : trips) {
            diff[t[2]] += t[0];
            diff[t[1]] -= t[0];
            s.insert(t[1]);
            s.insert(t[2]);
        }
        vector<int> points(s.begin(), s.end());
        sort(points.rbegin(), points.rend());
        int sum = 0;
        for (auto i : points) {
            int rest = capacity - diff[i] - sum;
            if (rest < 0) return false;
            sum += diff[i];
        }
        return true;
    }
};

不过由于需要给点进行排序，因此时间复杂度变成了 O(nlogn)，尽管如此，当整个路段很稀疏时，我们的应该是要更快的。

Links: leetcode-1094-car-pooling