Request begin/end日志：最早已完成请求优先输出

题意与假设

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

• requestID唯一且可比较，begin/end时间由调用者提供，可乱序完成但每请求end≥begin。
• take_completed只取当前完成集中end最早者；全局时间排序若未来还能迟到旧事件，需要水位线或等待流结束。

解题路线

1. active保存开始时间，end查找并删active，将(end,id,start)压最小堆。done集拒绝ID再次使用；若生产ID复用需版本。
2. take返回堆顶，平局按ID确定。未知end、重复begin和时间倒置都拒绝；异常前不修改有效active状态。
3. 全局日志“按end永远递增”与在线即时输出不能在无限乱序下同时保证。可在watermark之前释放完成日志，或离线收全后排序。等待中的请求不能占完成堆。

手动走一遍

A开始1结束9，B开始2结束6，均收到完成后先输出B(2,6)，再A(1,9)。已输出end9后收到end5，当前集合同仍可返回5，但它不是全局有序流。

Python 参考实现

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

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

from heapq import heappush,heappop
class Requests:
    def __init__(self):self.active={};self.done=set();self.heap=[]
    def begin(self,key,time):
        if key in self.active or key in self.done:raise ValueError("duplicate request")
        self.active[key]=time
    def end(self,key,time):
        if key not in self.active:raise ValueError("not active")
        start=self.active[key]
        if time<start:raise ValueError("end precedes start")
        del self.active[key];self.done.add(key);heappush(self.heap,(time,key,start))
    def take_completed(self):
        # Earliest end among completions currently received, not all future events.
        if not self.heap:return None
        end,key,start=heappop(self.heap);return key,start,end

复杂度

begin期望O(1)，end/take O(logC)，C待输出完成数；active/done/heap空间O(N)，done永久保留需生命周期清理。

易错点与追问

容易失分的边界

• heap以start做键会按错目标。
• 拿处理时机器now代替业务事件timestamp会掩盖迟到语义。

继续深挖

• 多线程begin/end如何防同ID双重完成？
• 日志落盘失败如何定义重试幂等与确认时机？