1094. 拼车
题目描述
一辆车最开始有 capacity 个空座位，只能一路向东开，不能掉头。
输入整数 capacity 和数组 trips。其中第 i 项为 [numPassengersi, fromi, toi]，意思是有 numPassengersi 位乘客要在距起点 fromi 公里处上车、在 toi 公里处下车。
在同一地点，先让到站的乘客下车，再让新乘客上车。行驶途中任何时刻车上人数都不能超过 capacity。能接送完所有乘客返回 true，否则返回 false。
示例 1
输入：trips = [[2,1,5],[3,3,7]], capacity = 4 输出：false
解释：在 3 到 5 公里之间车上有 2 + 3 = 5 人，超过 4 个座位。
示例 2
输入：trips = [[2,1,5],[3,3,7]], capacity = 5 输出：true
解释：最多同时 5 人，正好不超过座位数。
数据范围
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengersi <= 1000 <= fromi < toi <= 10001 <= capacity <= 10^5
解题思路：差分数组
位置只有 0–1000，可以用差分数组。每段行程在上车点 diff[from] += num，在下车点 diff[to] -= num。然后从西向东累加，前缀和 cur 就是车开过该位置时车上的人数，只要某处 cur > capacity 就返回 false。先加上车、再减下车在同一个 diff 格子里合并完成，恰好体现“先下后上”。
为什么正确
处理完位置 p 后，cur = diff[0] + ... + diff[p] = 从 p 开往 p+1 时车上的乘客数。
复杂度分析
时间 O(n + 1001)，空间 O(1001)。
易错点
乘客在 to 位置已经下车，所以行程占用的是半开区间 [from, to)，减法要写在 diff[to] 而不是 diff[to+1]，否则 [[2,1,5],[3,5,7]] capacity=3 会被错误判为超载。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
diff = [0] * 1001
for num, a, b in trips:
diff[a] += num
diff[b] -= num
cur = 0
for d in diff:
cur += d
if cur > capacity:
return False
return Trueclass Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[] diff = new int[1001];
for (int[] t : trips) {
diff[t[1]] += t[0];
diff[t[2]] -= t[0];
}
int cur = 0;
for (int d : diff) {
cur += d;
if (cur > capacity) {
return false;
}
}
return true;
}
}class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> diff(1001, 0);
for (auto& t : trips) {
diff[t[1]] += t[0];
diff[t[2]] -= t[0];
}
int cur = 0;
for (int d : diff) {
cur += d;
if (cur > capacity) {
return false;
}
}
return true;
}
};func carPooling(trips [][]int, capacity int) bool {
diff := make([]int, 1001)
for _, t := range trips {
diff[t[1]] += t[0]
diff[t[2]] -= t[0]
}
cur := 0
for _, d := range diff {
cur += d
if cur > capacity {
return false
}
}
return true
}var carPooling = function(trips, capacity) {
const diff = new Array(1001).fill(0);
for (const [num, a, b] of trips) {
diff[a] += num;
diff[b] -= num;
}
let cur = 0;
for (const d of diff) {
cur += d;
if (cur > capacity) {
return false;
}
}
return true;
};function carPooling(trips: number[][], capacity: number): boolean {
const diff: number[] = new Array(1001).fill(0);
for (const [num, a, b] of trips) {
diff[a] += num;
diff[b] -= num;
}
let cur = 0;
for (const d of diff) {
cur += d;
if (cur > capacity) {
return false;
}
}
return true;
}其他解法
两种方法的核心都是“在端点记录变化量再累加”。差分数组把变化量按下标放在数组里，适合位置范围小的情况；事件排序只处理真正出现的端点，适合位置范围大或不是整数的情况。
解法 2：事件排序扫描线 时间 O(n log n)，空间 O(n)
把每段行程拆成两个事件：在上车点乘客增加 num，在下车点乘客减少 num。按位置排序，位置相同时先处理下车（变化量为负的排在前面），因为在同一点下车的乘客会先让出座位。按顺序累加变化量，任何时刻超过座位数就返回 false。
复杂度只和行程数量有关，位置范围很大（如 10^9）时依然适用。本题位置不超过 1000，排序反而比差分数组多一个 log 因子。
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
events = []
for num, a, b in trips:
events.append((a, num))
events.append((b, -num))
events.sort()
cur = 0
for _, delta in events:
cur += delta
if cur > capacity:
return False
return Trueclass Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[][] events = new int[trips.length * 2][];
for (int i = 0; i < trips.length; i++) {
events[2 * i] = new int[]{trips[i][1], trips[i][0]};
events[2 * i + 1] = new int[]{trips[i][2], -trips[i][0]};
}
Arrays.sort(events, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
int cur = 0;
for (int[] e : events) {
cur += e[1];
if (cur > capacity) return false;
}
return true;
}
}class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<pair<int, int>> events;
for (auto& t : trips) {
events.push_back({t[1], t[0]});
events.push_back({t[2], -t[0]});
}
sort(events.begin(), events.end());
int cur = 0;
for (auto& e : events) {
cur += e.second;
if (cur > capacity) return false;
}
return true;
}
};func carPooling(trips [][]int, capacity int) bool {
events := make([][2]int, 0, len(trips)*2)
for _, t := range trips {
events = append(events, [2]int{t[1], t[0]}, [2]int{t[2], -t[0]})
}
sort.Slice(events, func(i, j int) bool {
if events[i][0] != events[j][0] {
return events[i][0] < events[j][0]
}
return events[i][1] < events[j][1]
})
cur := 0
for _, e := range events {
cur += e[1]
if cur > capacity {
return false
}
}
return true
}var carPooling = function(trips, capacity) {
const events = [];
for (const [num, a, b] of trips) {
events.push([a, num]);
events.push([b, -num]);
}
events.sort((x, y) => x[0] - y[0] || x[1] - y[1]);
let cur = 0;
for (const [, delta] of events) {
cur += delta;
if (cur > capacity) return false;
}
return true;
};function carPooling(trips: number[][], capacity: number): boolean {
const events: number[][] = [];
for (const [num, a, b] of trips) {
events.push([a, num]);
events.push([b, -num]);
}
events.sort((x, y) => x[0] - y[0] || x[1] - y[1]);
let cur = 0;
for (const [, delta] of events) {
cur += delta;
if (cur > capacity) return false;
}
return true;
}