Netflix 闭区间覆盖：最大重叠数与频繁点查询

题意与假设

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

• 输入每个区间 `[start,end]` 都含两端，允许零长度 `[x,x]`；start>end 报错。
• 求的是最大覆盖数，不要求输出达到最大值的全部点；若要求输出，扫描时记录坐标。
• 点查询的区间集合静态，建索引后可反复查询；若支持动态插入删除，需其他数据结构。

解题路线

1. 最大覆盖数：每段产生 `(start,+1)` 与 `(end,-1)`，同坐标必须先处理所有 start 再处理 end，更新过程中的最大 active。这样 `[1,2]` 与 `[2,3]` 在点 2 同时被计入。
2. 频繁点查询：分别排序所有 start 和 end。覆盖 t 的区间数等于 start≤t 的条数减去 end<t 的条数，用 `bisect_right(starts,t) - bisect_left(ends,t)`。
3. 若端点只有离散整数，也可在 end+1 做 -1 的差分，但要防最大整数溢出；连续时间坐标或浮点时间戳不应靠 end+1。

手动走一遍

区间 `[1,2]、[2,3]、[2,2]` 在 t=2 都覆盖，最大值 3；t=1.5 只有第一段。若同坐标先结束后开始，扫描时会误把 t=2 的最大覆盖漏掉。

Python 参考实现

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

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

from bisect import bisect_left, bisect_right


def maximum_closed_interval_overlap(intervals):
    events = []
    for start, end in intervals:
        if start > end:
            raise ValueError("interval start exceeds end")
        events.append((start, 0, 1))  # starts before ends at the same point
        events.append((end, 1, -1))
    active = best = 0
    for _, _, delta in sorted(events):
        active += delta
        best = max(best, active)
    return best


class ClosedIntervalCoverageIndex:
    def __init__(self, intervals):
        for start, end in intervals:
            if start > end:
                raise ValueError("interval start exceeds end")
        self.starts = sorted(start for start, _ in intervals)
        self.ends = sorted(end for _, end in intervals)

    def count_at(self, point):
        return bisect_right(self.starts, point) - bisect_left(self.ends, point)

复杂度

n 段区间排序事件 O(n log n)，扫描 O(n)；静态点查询索引构建 O(n log n)、空间 O(n)，每次查询 O(log n)。动态更新时两个 Python 排序数组插入 O(n)，不能宣称同样复杂度。

易错点与追问

容易失分的边界

• 使用半开 `[start,end)` 的同坐标结束先行规则。
• 闭区间端点用 end+1，但时间是浮点数或最大整数。
• 点查询减去 `ends≤t`，错误扣除恰在 t 结束的区间。
• 区间 `[x,x]` 被漏掉或算为零长度空集。
• 把静态二分方案直接用于高频动态更新。

继续深挖

• 若查询点来自有限离散坐标，怎样坐标压缩并做前缀和？
• 如果要支持实时 add/remove 与 point query，可怎样用平衡树维护带子树和的事件？
• 同一时间有成千上万重复端点时如何成组处理而不是逐事件返回？