1094. 拼车（Car Pooling）

频次 ★★★ · 难度 🟡 · 高频：快手

题目

[num, from, to] 表示上客数/上客点/下客点，容量 capacity，能否全程不超载。

思路

差分数组：diff[i] 表示 i 点的人数变化，遍历 trips 更新上下客；然后前缀和模拟看全程。

代码

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;
}

复杂度

• 时间：O(n + 1000)
• 空间：O(1000)

边界条件

• to 点下车，不占 to 这一站的座位。所以是 diff[to] -= num 而不是 diff[to+1] -= num——乘客占用的是左闭右开区间 [from, to)。这与 1109. 航班预订统计 的闭区间正好相反
• from == to：零长度区间，diff 上加了又减，净效果为 0，天然正确
• 数组开 1001：题目保证站点 0 ≤ from < to ≤ 1000，diff[1000] 要能写下
• 首站就超载：单个 trip 的 num > capacity，第一次前缀和就返回 false

变式

• 1109. 航班预订统计：同样的差分，但区间是闭的，且要求输出每个位置的最终值
• 求最大同时在车人数：不判 capacity，直接取前缀和的最大值——这就是「会议室 II」的另一种解法
• 站点坐标范围极大（比如 10^9）：差分数组开不下，改用「事件排序 + 扫描线」：把 (from, +num) 和 (to, -num) 作为事件按坐标排序后扫一遍，O(n log n)
• 区间加、单点查：差分的标准用法；反过来「单点加、区间查」是前缀和；两者都要就上树状数组

易错点

• diff[to] -= num，不是 diff[to] -= 1：减掉的是这一趟的人数，不是趟数
• 把差分和前缀和搞反：diff 记的是变化量，要靠前缀和累加才还原成「当前车上人数」。只看 diff 数组本身没有任何意义
• 判超载必须在累加之后立刻判，不能先累加完整个数组再找最大值——虽然本题两者结果相同，但提前返回能省一半遍历

面试追问

• 差分和前缀和是什么关系：互为逆运算。前缀和把「点值」变成「区间和」，差分把「区间修改」变成「两个点修改」。一次区间加从 O(区间长度) 降到 O(1)，代价是最后要 O(n) 还原一次。 所以差分适合「先批量改、最后统一读」，不适合边改边查。
• 为什么这题是 [from, to) 而 1109 是 [first, last]：因为语义不同。拼车的乘客在 to 站下车，那一刻他不再占座；航班预订的 last 是最后一个预定的航班，它算数。差分的端点怎么写，完全由题目的区间开闭决定，不是模板问题。 这是这类题唯一真正的考点。
• 不用差分能做吗：能，对每个 trip 暴力遍历 [from, to) 累加，O(n × 站点数)。差分把每个 trip 的处理从 O(区间长) 降到 O(1)。
• 和限流的滑动窗口计数有关系吗：有。「统计某时刻有多少请求在窗口内」也是区间覆盖计数，差分/扫描线是同一套工具，见系统设计的限流算法。

关联题

• 同套路：1109. 航班预订统计