题目描述

You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)

Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle’s initial location.

Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.

样例

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Example 3:

Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true

Example 4:

Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true

算法1

sort + heap, $O(nlogn)$

sort by start + 小顶堆。 小顶堆 存 区间的end，遍历到一个新区间时, 将当前区间的start 之前结束的区间 从 堆中 pop出去, 并减去其乘客数。 然后 push 当前区间，并累加加乘客数。任意时刻堆中的乘客数都需要小于capacity。

C++ 代码

    bool carPooling(vector<vector<int>>& trips, int capacity) {
        if(trips.size()==0) return true;
        if(capacity == 0) return false;

        // sort by start 
        sort(begin(trips), end(trips), [](const auto& a, const auto& b) { return a[1] < b[1]; });

        // manage the ends with min heap 
        using TPair = pair<int, int>; // (end time, num_passengers)
        priority_queue<TPair, vector<TPair>, function<bool(const TPair&, const TPair&)>> pq(
            [](const TPair& a, const TPair& b) { return b.first < a.first; }
        );

        int needed = 0;
        for(const auto& t : trips) {
            while(pq.size() && pq.top().first <= t[1]) { 
                needed -= pq.top().second;
                pq.pop();
            }

            pq.push({ t[2], t[0] });
            needed += t[0];
            if(needed > capacity) return false;
        }

        return true;
    }

算法2

tree map $O(nlogn)$

用 tree map 记录 event 发生时刻乘客数的变化，检查任意时刻 需要的 seats 是否超过 capacity。
map: time -> 乘客数变化值。 map的遍历时按照时间顺序的，累计计算乘客数即可。

例如： [[3,2,7],[3,7,9],[8,3,9]]
时间: 2, 3, 7, 9
乘客变化数: 3, 8, 0, -11
累计乘客数: 3, 11, 11, 0

C++ 代码

    bool carPooling(vector<vector<int>>& trips, int capacity) {
        if(trips.size()==0) return true;
        if(capacity == 0) return false;

        map<int, int> m; // time --> num passenger

        for(const auto t : trips) {
            m[t[1]] += t[0];
            m[t[2]] -= t[0];
        }

        int acc = 0;
        for(const auto& p : m) {
            acc += p.second;
            if(acc > capacity) return false;
        }
        return true;
    }