拼车（1094）

1094. 拼车 - 力扣（LeetCode）

解法：

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) 
    {
        uint32_t passenger_cnt = 0;
        //将原数据按照from排序
        auto func_0 = [](vector<int> & i1, vector<int> & i2) {
            return i1[1] < i2[1];
        };
        sort(trips.begin(), trips.end(), func_0);

        //入队列的数据按照to排序
        auto func_1 = [](pair<int, int> & i1, pair<int, int> & i2) {
            return i1.second > i2.second;
        };
        vector<pair<int, int>> v;
        //给优先队列预先分配内存
        v.reserve(trips.size());
        //priority_queue 只需要记录 count 和 离开的时间
        priority_queue<pair<int, int> , vector<pair<int, int>>, decltype(func_1)> q( func_1, v);
        
        for (int i = 0; i < trips.size(); ++i) {
            //如果队列的top()数据小于trips[i][1]，说明在trips[i][1]上车前top()已经下车
            while (!q.empty() && (q.top().second <= trips[i][1])){
                passenger_cnt -= q.top().first;
                q.pop();
            }

            passenger_cnt += trips[i][0];
            if (passenger_cnt >  capacity) {
                return false;
            }
            q.emplace(trips[i][0], trips[i][2]);
        }

        return true;
    }
};

总结：

时间复杂度O(NlogN)，空间复杂度O(N)，算法细节如代码注释。