拼车问题怎么用差分或扫描线判断是否超载？（LeetCode 1094）

简化版

拼车问题把每段行程看成半开区间 [from, to) 的人数增减。可以用差分数组：diff[from] += passengers，diff[to] -= passengers，最后按站点前缀累加，任意位置超过 capacity 就返回 false。

详细版

每个 trip 是 [numPassengers, from, to]，表示从 from 上车，到 to 下车，所以乘客占用的是 [from, to)，在 to 点已经不在车上。若站点范围较小，用差分数组最简单。

也可以把上下车拆成事件：(from, +p)、(to, -p)，按位置排序扫描。若同一位置既有人下车又有人上车，半开区间语义要求先下再上，或者直接把同位置增减合并后再判断。

差分数组时间 O(M + R)，R 是站点最大范围；事件扫描时间 O(M log M)，M 是行程数。面试时优先说清半开区间和同点上下车顺序。

完整版教学

一、为什么这是区间增减问题

每个行程不是一个单点操作，而是在一段路上持续占用座位。比如 [2,1,5] 表示 2 名乘客在站点 1 到 5 之间都在车上。

这等价于对区间 [1,5) 的载客量加 2。多个行程叠加后，只要任意位置载客量超过 capacity，拼车就不可行。

记忆钩子：拼车不是检查每个 trip 本身，而是检查所有 trip 叠加后的“车上人数曲线”。

二、半开区间为什么重要

乘客在 from 上车，在 to 下车，到了 to 这个点后就不占座。因此占用区间是 [from, to)，不是 [from, to]。

trip A: 2人 [1,5)
trip B: 3人 [5,7)
在站点 5: A 已下车，B 上车，不同时占座

如果误把它当闭区间，会把站点 5 的人数算成 5，可能错误判定超载。

三、差分数组写法

差分数组适合站点范围有限的情况。上车是区间起点加人数，下车是区间终点减人数。

boolean carPooling(int[][] trips, int capacity) {
    int[] diff = new int[1001];
    for (int[] t : trips) {
        int p = t[0], from = t[1], to = t[2];
        diff[from] += p;
        diff[to] -= p;
    }

    int cur = 0;
    for (int x : diff) {
        cur += x;
        if (cur > capacity) return false;
    }
    return true;
}

LeetCode 原题站点范围可用 1001。如果真实业务位置范围很大，差分数组会浪费空间，应换事件排序或 TreeMap。

四、扫描线事件写法

事件法把每次上下车看成一个点事件：

(from, +p)
(to, -p)
按位置升序扫描，累加车上人数

若同一位置有多个事件，可以先用 TreeMap 把增减合并，再扫描：

TreeMap<Integer, Integer> events = new TreeMap<>();
for (int[] t : trips) {
    events.merge(t[1], t[0], Integer::sum);
    events.merge(t[2], -t[0], Integer::sum);
}
int cur = 0;
for (int delta : events.values()) {
    cur += delta;
    if (cur > capacity) return false;
}

合并同点事件后，先下后上的问题自然被抵消。比如同一点 -2 和 +3 合并为 +1，反映了经过这个点后的净变化。

五、数字例子手推

trips = [[2,1,5],[3,3,7]], capacity = 4：

站点	diff 变化	当前人数
1	+2	2
3	+3	5
5	-2	3
7	-3	0

在站点 3 到 5 之间车上人数是 5，超过容量 4，所以返回 false。这个表就是扫描线的“人数曲线”。

六、差分数组和扫描线怎么选

做法	时间复杂度	空间复杂度	适用场景
差分数组	O(M + R)	O(R)	坐标范围小
事件排序	O(M log M)	O(M)	坐标范围大
TreeMap 合并事件	O(M log M)	O(M)	需要处理同点合并

R 是站点坐标范围，M 是 trip 数量。面试中如果题目给出坐标上限，差分数组很简洁；如果没有上限，事件扫描更稳。

七、常见误区与追问

误区：把行程当成闭区间 [from,to]。 乘客到 to 已下车，占用应是 [from,to)。
误区：只检查每个 trip 的人数是否超过容量。 多个 trip 会叠加，单个不超不代表整体不超。
误区：同一站点上车下车顺序随便处理。 半开语义下到站先释放旧乘客，再计算新乘客更合理；合并事件可避免顺序错误。
追问：坐标范围很大怎么办？ 不用数组，改用排序事件或 TreeMap。
追问：为什么差分在 to 位置减人？ 因为 [from,to) 不包含 to，乘客从 to 开始不占座。
追问：如果要返回最大载客量怎么办？ 扫描时维护 max(cur)，不只判断是否超过容量。

八、加强记忆

拼车问题就是区间叠加后的容量检查。from 加人、to 减人，前缀和得到每段路上的车上人数；任何位置超过 capacity 就失败。坐标小用差分数组，坐标大用扫描线事件，始终记住行程是半开区间 [from,to)。

简化版

详细版