Meta Carpool容量：上下车事件与同站交接

题目重点：将每段乘客区间转为位置差分，扫描验证全程人数不超过容量。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练trip=(people,start,end)、start<end，people/capacity非负；乘客占用[start,end)，同位置先下车再上车，可复用座位。

解题路线

每trip在start加people，在end减people，按位置累加并检查capacity。把同坐标delta先合并，得到离开该站后的负载，避免同站上车先处理制造瞬间假超载。
每两个相邻事件之间乘客人数不变，只需要检查事件更新后的状态，不按每米/每分钟迭代。
不同trip顺序不影响结果；大量相同点先聚合减小排序集合。start=end本合同拒绝而不是误把零长段算占座。
若要求返回首次超载位置，扫描时记录该point与负载；若区间为闭合或服务不能即时交接，不能复用同位置净差政策。

手动走一遍

容量2，trip(2,1,5)和(2,5,8)可行，因为站5先下两人再上两人。若第二trip从4开始，则[4,5)共4人超载。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import defaultdict


def can_carpool(trips,capacity):
    """(passengers,start,end), half-open [start,end), dropoff at start before pickup.

    Nonnegative passenger counts/capacity, start<end. Input order irrelevant.
    """
    if capacity<0:raise ValueError('negative capacity')
    events=defaultdict(int)
    for people,start,end in trips:
        if people<0 or start>=end:raise ValueError('invalid trip')
        events[start]+=people;events[end]-=people
    aboard=0
    for point in sorted(events):
        aboard+=events[point]
        if aboard>capacity:return False
    return True

复杂度

O(T log T)时间/O(T)事件空间；若位置范围小可用差分数组O(T+R)，R巨大时不合适。不能把聚合后的sort漏计而标线性。

易错点与追问

容易失分的边界

同站加减不合并且按加先排序，会把合法交接误判。
暴力走每个位置的复杂度依赖路线长度，无法适应大坐标。

继续深挖

实时新增trip怎样用范围加/全局max结构查询？
如果车辆容量沿途变化，容量变更也应作为事件并明确先后。