题目描述

假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许 掉头或改变方向，你可以将其想象为一个向量）。

这儿有一份行程计划表 trips，其中 trips[i] = [num_passengers, start_location, end_location] 包含了你的第 i 次行程信息：

• 必须接送的乘客数量；
• 乘客的上车地点；
• 以及乘客的下车地点。

这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所用乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。

样例

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true

输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true

提示

1. trips.length <= 1000
2. trips[i].length == 3
3. 1 <= trips[i][0] <= 100
4. 0 <= trips[i][1] < trips[i][2] <= 1000
5. 1 <= capacity <= 100000

算法

(区间标记) $O(n + m)$

1. 我们采用区间两端点标记的方法表示区间整体的加减。
2. 这道题每次给出一段左闭右开区间 [x, y) 代表 [x, y - 1] 闭区间内要能增加 k 个人。
3. 我们在 x 位置上增加 k 个人，然后在 y 位置上减少 k 个人。对于每个这样的区间区里完毕后，求整个数组的前缀和。
4. 求完前缀和后，每个点就代表当前点需要承受的乘客数。扫一遍所有点判断有没有超过 capacity 即可。

时间复杂度

• 每段区间遍历一次，时间复杂度为 $O(n)$。
• 每个点遍历一次，时间复杂度为 $O(m)$，$m$ 为总区间长度。
• 故总时间复杂度为 $O(n + m)$。

空间复杂度

• 需要定义一个累计数组，故时间复杂度为 $O(m)$。

C++ 代码

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> seats(1001, 0);
        int n = trips.size();

        for (int i = 0; i < n; i++) {
            seats[trips[i][1]] += trips[i][0];
            seats[trips[i][2]] -= trips[i][0];
        }

        if (seats[0] > capacity)
            return false;

        for (int i = 1; i <= 1000; i++) {
            seats[i] += seats[i - 1];
            if (seats[i] > capacity)
                return false;
        }

        return true;
    }
};