Meta 司机动作配送时长：分司机时钟与多订单

题目重点：根据travel/pickup/dropoff动作和地点行驶时间，计算每个订单从取餐到交付的耗时。

题意与假设

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

训练动作按每司机时间顺序提供，travel只有目的location，pickup/dropoff只有orderId；初始位置显式给定，travelTimes有方向。未给等待/服务时间，本模型只累加行驶时间。
每订单同司机pickup后dropoff，无换手，未完成订单不输出假0；pickup→dropoff而非接单→送达定义应确认。

解题路线

每司机维护location和clock，travel查(from,to)时长、clock增加并更新location。不同司机穿插动作不能共享一个总时钟。
pickup记录order→(driver,clock)，dropoff验证相同driver且存在pickup，再输出clockNow−pickupClock，标finished防重复pickup。
同车多订单共享路段，因此一段travel可能同时增加多个订单等待时间，但无需每次更新所有订单，起点时钟差已自然计入。
缺route不能默认为0，否则低估配送；路线反向是否同时间需合同明确，不自动用对称矩阵。无时长pickup服务在训练中0，若给实际timestamp则应直接按事件时间差而非加估计路程。
重复动作、司机未知、跨司机dropoff需要拒绝或按输入异常策略处理；本例拒绝。不完整pickup留未完成状态，避免把在途订单当已交付。

手动走一遍

司机d起点0，pickup A；travel0→1耗10，pickup B；travel1→2耗5，dropoff A；再travel2→3耗3，dropoff B。A=15分钟，B=8；两订单共享后半路但起算时点不同。

Python 参考实现

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

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

def delivery_durations(events,travel_times,initial_locations):
    """Training events are in per-driver order; no explicit waits/service duration.

    travel: driver/action/location_id; pickup/dropoff: driver/action/order_id.
    Directed travel_times[(from,to)] in nonnegative minutes. No driver handoffs.
    Duration measures pickup to dropoff elapsed modeled travel time.
    """
    location=dict(initial_locations);clock={d:0 for d in location};onboard={};finished={}
    for e in events:
        driver=e['driver'];action=e['action']
        if driver not in location:raise ValueError('initial location required')
        if action=='travel':
            target=e['location_id'];pair=(location[driver],target)
            if pair not in travel_times or travel_times[pair]<0:raise ValueError('missing/negative route duration')
            clock[driver]+=travel_times[pair];location[driver]=target
        elif action=='pickup':
            order=e['order_id']
            if order in onboard or order in finished:raise ValueError('duplicate pickup')
            onboard[order]=(driver,clock[driver])
        elif action=='dropoff':
            order=e['order_id']
            if order not in onboard or onboard[order][0]!=driver:raise ValueError('missing/wrong-driver pickup')
            _,start=onboard.pop(order);finished[order]=clock[driver]-start
        else:raise ValueError('unknown action')
    # Incomplete orders remain missing; they do not receive a fake zero duration.
    return finished

复杂度

O(E)动作处理、O(D+O)司机/订单状态，route lookup平均O(1)，输入route表空间另计。输出O(已完成订单数)，不为每travel扫描所有在车订单。

易错点与追问

容易失分的边界

每driver共用clock导致穿插司机互相增加配送时间。
没有初始位置却默认某个0地点，隐含改变输入。

继续深挖

如果order可转交司机，handoff需要怎样保存累计已耗时而不重置？
实际等待/堵车timestamp存在时，估算时间与观测时间应分字段。