Uber VO 两份已排序时间区间求交：超长列表如何流式处理

题目重点：两份按起点排序的区间表求重叠，处理闭区间接触、同表内部重叠与数据大于内存的追问；给出流式归并加双指针生成器。

题意与假设

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

每个输入按区间起点非递减排序，允许同表内部相交；区间采用闭区间 [start,end]，start≤end，接触端点算一个点的交集。
输出为两份区间并集的交集，规范化为按起点排序、互不重叠的最大闭区间。若业务要求保留每对原始区间产生的交集片段，则输出口径需另定。
输入支持只读迭代器/外部文件流，不能随机访问；训练代码发现未排序或逆序端点会报错，不自行排序，因为排序会失去 O(1) 工作内存。

解题路线

先分别流式归并每份输入的内部重叠区间：维护当前 [lo,hi]，下一段起点≤hi 就延长右端，否则输出当前段并开始新段。每条流只保留一段状态。
给两条规范化流各取一个当前区间 A、B，交集候选为 [max(A.start,B.start), min(A.end,B.end)]；左端≤右端时输出。
推进右端更早的区间，因为它之后不可能与另一条流的后续区间相交；若两端相等则同时推进。归并后的每条流内部区间不重叠，因此生成的交集天然按序且不重复。
超内存时从磁盘顺序读入而非一次加载整表，用生成器逐段输出到文件或下游；若原始数据未排序，必须先外部归并排序，不能再宣称整个流程只用常数内存。

手动走一遍

A=[(0,10),(20,30)]、B=[(5,8),(15,22)]：首段求交为 (5,8)，B 的右端 8 更早，推进 B；随后 A 第一段与 B 第二段不交，推进 A；最后得 (20,22)。如果 A 内部另有 (9,12)，先与 (0,10) 归并为 (0,12)。

Python 参考实现

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

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

"""Intersect unions of two sorted interval streams with constant working space."""

from collections.abc import Iterable, Iterator


def merged(intervals: Iterable[tuple[int, int]]) -> Iterator[tuple[int, int]]:
    current: tuple[int, int] | None = None
    previous_start: int | None = None
    for start, end in intervals:
        if start > end:
            raise ValueError("interval start exceeds end")
        if previous_start is not None and start < previous_start:
            raise ValueError("intervals must be sorted by start")
        previous_start = start
        if current is None:
            current = (start, end)
        elif start <= current[1]:
            current = (current[0], max(current[1], end))
        else:
            yield current
            current = (start, end)
    if current is not None:
        yield current


def intersections(
    left: Iterable[tuple[int, int]], right: Iterable[tuple[int, int]]
) -> Iterator[tuple[int, int]]:
    a_iter, b_iter = merged(left), merged(right)
    a, b = next(a_iter, None), next(b_iter, None)
    while a is not None and b is not None:
        start, end = max(a[0], b[0]), min(a[1], b[1])
        if start <= end:
            yield (start, end)
        if a[1] < b[1]:
            a = next(a_iter, None)
        elif b[1] < a[1]:
            b = next(b_iter, None)
        else:
            a, b = next(a_iter, None), next(b_iter, None)

复杂度

输入段数分别 n、m，归并与求交合计 O(n+m) 时间；忽略输入/输出流的缓冲，只保留两段和迭代器状态，工作空间 O(1)。若把输出 list 化，额外 O(r)，r 为结果段数。

易错点与追问

容易失分的边界

两指针直接用‘仅排序’的原始列表，却暗中假设每份列表内部区间互不重叠；可能重复输出或误判应规范化的结果。
写成 start<end 会丢掉闭区间在单点相触的交集；若实际是半开时间段 [start,end)，则应使用严格小于。
为回答大文件追问仍先把两表读进数组，或先在内存 sort，违背流式规模条件。
对有序数据使用所有区间两两比较 O(nm)，错失推进较早结束端点的线性解。

继续深挖

若要求统计重叠总时长，闭区间用连续时间长度 end−start；整数日期若两端都算一天则需 end−start+1，不能混用。
若输入分布在多个已排序文件，可先做 k 路外部归并，再接这条流式交集管线。
若是在线不断插入与删除区间，不再是单次扫描；可讨论有序区间索引和增量更新。