Meta 租车预订去冲突：按输入顺序接受或拒绝

题目重点：逐条判断预订与已接受日期是否重叠，避免排序改变先到先接受政策。

题意与假设

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

训练单辆车/一个独占资源，预订id唯一、ISO日期；区间为闭区间[pickup,dropoff]，同一天交接算重叠。实际题面若还车当天可再租，应改为半开区间，不能猜端点。
按输入顺序处理，不优化最多可接受订单数；输出每id与bool，可格式化accept/rejected。

解题路线

已接受区间互不重叠，维护按start排序的starts和accepted。新预订bisect找到插入位，只需看前驱end≥start或后继start≤end是否冲突。
前驱和后继足够：更早区间end不超过前驱start，更晚区间start不早于后继；互不重叠不变量使两邻检查覆盖所有可能。
被拒绝的区间不写入接受集；不能因为与某个已拒订单相交就继续拒。逐条插入的时间政策优先于按开始日期重排。
Python list插入需要移动元素O(N)，虽然bisect定位O(log N)，整个算法最坏O(N²)。如果题目必须O(N log N)，换带前驱/后继的平衡树；不把list假称有序树。

手动走一遍

输入10:[1,3]、11:[4,5]、12:[2,5]依次接受10/11、拒12。若先来了[3,5]再[1,4]，按输入先接受前者；先sort by start会颠倒政策。

Python 参考实现

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

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

from bisect import bisect_left
from datetime import date


def decide_reservations(reservations):
    """One resource, closed date intervals, process input order (not start order).

    IDs unique, ISO dates. A same-day handoff overlaps in this training contract.
    """
    accepted=[];starts=[];seen=set();result=[]
    for record in reservations:
        ident=record['id'];start=date.fromisoformat(record['pickup_date']);end=date.fromisoformat(record['dropoff_date'])
        if start>end or ident in seen:raise ValueError('invalid dates or repeated id')
        seen.add(ident);position=bisect_left(starts,start)
        overlap=(position>0 and accepted[position-1][1]>=start) or (position<len(accepted) and accepted[position][0]<=end)
        result.append((ident,not overlap))
        if not overlap:starts.insert(position,start);accepted.insert(position,(start,end))
    return result

复杂度

当前基线每次检索O(log A)但插入O(A)，总最坏O(N²)、空间O(N)。日期解析和输出也按记录数；独立测试按已占用天集合验证闭区间。

易错点与追问

容易失分的边界

按pickup排序后判冲突，会改变原始接受先后。
只检前驱漏新预订跨后继的情况。

继续深挖

多车分配先要明确是否可选任意车与车型，单资源判断不能直接扩大。
允许同日交接时，前驱end>start、后继start<end替代闭区间比较，并明确零长度租赁。