拼车（Car Pooling）

题目描述

车上最初有 $capacity$ 个空座位，汽车只能 ​** 一直向东行驶（不能掉头）** ​。

给定一个数组 $trips$，其中每个元素表示为：

$$trips[i] = [numPassengers, from, to]$$ $$$$

含义如下：

• $numPassengers$：乘客数量
• $from$：上车位置
• $to$：下车位置

位置单位为 ​ * *距离起点向东的公里数 * *​。

请判断在整个行程过程中，是否始终满足：

$$text{ 车上乘客数 } le capacity$$

如果满足，输出 true；否则输出 false。

---

输入格式

• 第一行输入一个整数 $n$，表示行程数量
• 接下来 $n$ 行，每行输入三个整数：

$$numPassengers from to$$

• 最后一行输入一个整数 $capacity$

---

输出格式

• 输出一个布尔值：
• true 表示可以完成所有拼车任务
• false 表示无法完成

---

样例输入 1

2
2 1 5
3 3 7
4

样例输出 1

false

样例解释 1

位置 1：上车 2 人 → 当前 2 人
位置 3：上车 3 人 → 当前 5 人 > capacity

因此无法完成。

---

样例输入 2

2
2 1 5
3 3 7
5

样例输出 2

true

样例解释 2

位置 1：上车 2 人 → 当前 2 人
位置 3：上车 3 人 → 当前 5 人
位置 5：下车 2 人 → 当前 3 人
位置 7：下车 3 人 → 当前 0 人

全程未超过容量。

数据范围

$$1 \le n \le 1000$$ $$1 \le numPassengers \le 100$$ $$0 \le from < to \le 1000$$ $$1 \le capacity \le 100000$$

提示

可以使用 * *差分 + 前缀和 * *来模拟每个位置的乘客变化：

• 在 $from$ 位置加上乘客数
• 在 $to$ 位置减去乘客数

然后对整个数组做前缀和，检查是否有超过 $capacity$ 的情况。

时间复杂度为：

$$O(n + 1000)$$