插入并合并订单簿价格档位区间

某做市引擎把订单簿维护为一组按 start 升序、两两不相交的价格档位区间,每个 [start, end] 代表做市方愿意在该连续 tick 段以聚合后的统一规模挂单。当一笔新的静止挂单到来时——无论是客户新单还是重定价事件——它会以单个区间 new_level = [s, e] 的形式投递进来。订单簿必须吞入这个新区间,与所有相切或相交的已有档位合并,合并后的簿仍然按 start 升序排列且两两不相交。

实现 solution(levels: list[list[int]], new_level: list[int]) -> list[list[int]]。闭区间语义:只要 a.end >= b.start 就合并(所以 [1, 5] 和 [5, 9] 塌缩为 [1, 9])。因为 levels 已经排好序且不相交,所做的工作就是一次线性扫描——O(N) 时间、O(N) 输出、不需要二次排序。算法形状是三段:把严格在 new_level 之前的档位原样复制,把与之相切/相交的连续段折叠成一个合并区间,再把严格之后的档位原样复制。

举例:solution([[1, 3], [6, 9]], [2, 5]) 返回 [[1, 5], [6, 9]]。新区间 [2, 5] 与 [1, 3] 相交(合并为 [1, 5]),然后严格位于 [6, 9] 之前,后者原样保留。

实践背景

把新到达的价格档位区间插入到一个按 start 升序、两两不相交的订单簿里,本质上就是教科书级别的插入区间问题(LeetCode 57)穿了一身微观结构的外衣。真实交易场所不会一行存一个 tick——做市方在一段连续 tick 段上挂同样的规模时,撮合引擎和公开深度行情都会把这一段压缩成一行 [start, end],簿的不变量就是"按 start 升序、两两不相交"。每一次下单、撤单、重定价,本质上都是一次"插入区间":定位与之相切/相交的连续段,折叠下来,再发出去。如果偷懒写成 levels + [new_level] → sort → 合并相交,每次更新 O(N log N),而且白白丢掉了调用方维护的"已排序"不变量。三段线性扫描才是低延迟订单簿的标准写法,而且它能直接推广到深度行情聚合、日历屏蔽段合并,以及任何一类"在流式插入下维护一组排序且不相交的覆盖"的问题。