拼车（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)，算法细节如代码注释。