餐厅候位：按到达顺序找到首个能入座的队伍

题意与假设

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

• 服务条件人数≤capacity；不拆队、不拼桌；只有活跃ID必须唯一，离开后重加入视为新到达。
• 源描述存在按桌尺寸适配的追问，本文明确采用first-fit最早可坐，而非人数最接近桌容量。

解题路线

1. 第一版用有序map保存ID→人数。join尾插、leave按ID删除，serve从最早开始扫描到首个合适组。
2. 这同时满足离开任意队伍和到达稳定顺序。不能用人数最小堆，因为它会让晚到的小组抢过早到可坐组。
3. 如服务量大，按人数维护FIFO队列，再用segment tree在size≤capacity范围取最小arrival序号；删除需要索引或lazy tombstone。复杂度随人数域/活跃人数而变。

手动走一遍

依次A4、B2、C3，桌容量3服务B；A继续等待，下一桌4服务A。A离开再加入后排在尚活跃C之后，而不是恢复旧位置。

Python 参考实现

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

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

class Waitlist:
    def __init__(self):
        self.groups = {}  # Insertion order is arrival order (Python 3.7+).

    def join(self, ident, size):
        if ident in self.groups or type(size) is not int or size <= 0:
            raise ValueError("unique active ID and positive size required")
        self.groups[ident] = size

    def leave(self, ident):
        return self.groups.pop(ident, None)

    def serve(self, capacity):
        if type(capacity) is not int or capacity <= 0:
            raise ValueError("positive capacity required")
        for ident, size in self.groups.items():
            if size <= capacity:
                del self.groups[ident]
                return ident, size
        return None

复杂度

基线join/leave期望O(1)，serve最坏O(n)，空间O(n)。当前serve找到后立刻返回，不继续使用已修改的dict迭代器。

易错点与追问

容易失分的边界

• 把桌剩余容量当新桌再次serve会改变不拼桌合同。
• 若ID可重复要给唯一ticket；仅用姓名无法安全删除。

继续深挖

• 人数域有限时如何用范围最小arrival查询做到O(logU)服务？
• 防止大组长期等待，应如何明确公平性目标及等待告警？