LinkedIn Meeting Scheduler：最早空档、排序预处理与并发预订

题目重点：在既有 booking 上求给定起点之后最早可容纳时长的区间，厘清插入、查询和线程安全成本。

题意与假设

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

训练代码约定 booking 为半开区间 [start,end)，不允许重叠；查询返回不早于 requested_start 的最早时刻，可无限往后排，duration>0。
题目说可通过 add booking 保序，并问 O(N) 查询；训练代码用二分找到起始位置、线性扫描。并发方案只作设计追问，没有声称原题要求锁的具体实现。

解题路线

插入时二分定位 start，检查前后相邻区间是否冲突；在 Python 数组中 insert 搬移元素 O(N)，二分查找 O(log N)，不能把整个插入误报 O(log N)。
查询先定位请求起点所在/后续第一个 booking。若当前时间落在上一段 booking 内，就跳到该段 end；依次看下一段 start，能容下 duration 则返回当前候选，否则跳到该 booking end。
每次候选时间只向右移动，排序确保一旦出现足够大空隙就已经是最早解。端点相接可安排，因为区间半开；重复预约需拒绝或依真实需求合并。
并发下‘查空档→插 booking’必须是同一原子操作：单实例锁或 DB 范围冲突约束/串行化事务。只给读取加锁而插入不加锁会双订。多机高写场景按房间/资源分区，先量测热点，再考虑 interval tree 或有序树。

手动走一遍

现有 [10,20)、[25,30)，请求 start=12、duration=5：落在首段，候选变 20；[20,25) 刚好放下，返回 20。若 duration=6，则跳过第二段返回 30。

Python 参考实现

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

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

from bisect import bisect_left


class MeetingScheduler:
    """Half-open bookings. Overlaps rejected; arbitrary integer time units."""

    def __init__(self):
        self.bookings = []

    def add_booking(self, start: int, end: int) -> None:
        if end <= start:
            raise ValueError("empty booking")
        i = bisect_left(self.bookings, (start, end))
        if i and self.bookings[i - 1][1] > start:
            raise ValueError("overlap")
        if i < len(self.bookings) and end > self.bookings[i][0]:
            raise ValueError("overlap")
        self.bookings.insert(i, (start, end))

    def earliest_start(self, requested_start: int, duration: int) -> int:
        if duration <= 0:
            raise ValueError("nonpositive duration")
        candidate = requested_start
        i = bisect_left(self.bookings, (candidate, float("-inf")))
        if i and self.bookings[i - 1][1] > candidate:
            candidate = self.bookings[i - 1][1]
        for start, end in self.bookings[i:]:
            if candidate + duration <= start:
                break
            candidate = max(candidate, end)
        return candidate

复杂度

N 段 booking，数组插入最坏 O(N) 搬移、空间 O(N)；查询二分 O(log N) 加后续扫描 O(K)，最坏 O(N)，额外空间 O(1)。若用平衡有序树，插入可 O(log N)，但语言标准库/并发语义须另选。

易错点与追问

容易失分的边界

只二分找 start，却忽略 requested_start 位于前一个 booking 中。
把 [end,next_start) 中 end 相接误判冲突。
把 Python list.insert 说成 O(log N)。
‘读后写’分两次锁导致竞态双订。
未询问 meeting 是否可重叠、是否有多会议室。

继续深挖

若新增 booking 极频繁，用什么有序结构？
多会议室情况下如何找全局最早槽？
如何保证并发请求不会同时预订同一空档？
时区与夏令时转换应放在输入层还是调度核心？