Merge Overlapping Quote-Validity Windows

某市场数据基础设施团队为每个标的缓存了报价有效期窗口 —— 即一条流式报价仍代表全市场最佳买卖价、尚未刷新或失效的时间区间。多个上游行情源会对同一标的发布重叠或相接的有效期窗口,缓存层需要把它们压缩为最少数量的不相交有效期区间,以保持查询索引的紧凑。

实现 solution(intervals: list[list[int]]) -> list[list[int]]。给定一组闭区间整数 [start, end],返回合并后按 start 升序排列的不相交区间集合。两个区间重叠或相接(即必须合并)的条件是 next.start ≤ current.end(闭区间语义:在单个端点相接就足以触发合并)。经典做法是先按起点排序,再扫描合并,时间复杂度 O(N log N),输出空间 O(N)。

例如,solution([[1, 3], [2, 6], [8, 10], [15, 18]]) 返回 [[1, 6], [8, 10], [15, 18]]:排序后 [1, 3] 与 [2, 6] 重叠(2 ≤ 3),合并为 [1, 6];[8, 10] 与 [15, 18] 互不相交。作为闭区间边界用例,solution([[1, 4], [4, 5]]) 返回 [[1, 5]] —— 在端点 4 处相接同样要合并。空输入返回 [],单个区间原样返回。

实际背景

合并重叠区间是 quant/行情工程师工作中频繁出现的基础原语:在流式报价缓存中去重报价有效期窗口、把连续的停牌时段压缩成单条记录、把 TWAP 调度器中相邻共享端点的执行桶合并、根据多个 prime broker 的可借券窗口计算总覆盖时间、为公司行动生效区间构建快速查询索引……算法很短 —— 排序 + 扫描 + 合并 —— 但生产中有两个细节最容易翻车:(1)闭区间还是半开区间必须与上游行情的约定完全一致,否则会悄悄把本应连续的段切碎(或反过来把本不该合并的段错误合并);(2)手写实现经常漏掉循环结束后的最后那段开区间。把经典模板烂熟于心,这些就再也不会成为 bug。