合并两条成交磁带
Merge Two Trade Tapes
开始编码做跨场所执行后的成交回放、或为 TCA(交易成本分析)准备一份统一的成交磁带时,常常要把两条来自不同场所的成交流合成一条全局按时间升序的磁带,并在每一笔上打上来源场所,方便下游按场所做归因。两条原始磁带通常各自已经是时间序的——它们就是从各自场所的行情链路上顺序解析出来的——但简单地把两条 concat 起来再 sort 既慢又掩盖了输入已经有序这个事实。
请实现 solution(tape_a: list, tape_b: list, venue_a: str, venue_b: str) -> list。tape_a 和 tape_b 是两条按时间升序排好的成交磁带,每条记录形如 [timestamp, price, qty]。venue_a 和 venue_b 是两个场所标签字符串。请把两条磁带合并成一条整体按 timestamp 升序排列的列表,列表中每个元素是 [timestamp, price, qty, venue]——也就是在原成交三元组末尾追加一个场所字段。**当某一刻 tape_a 队首和 tape_b 队首的时间戳完全相同时,输出顺序中 tape_a 的那一条排在前面**(稳定合并、A 优先);同一磁带内部并列时间戳之间的相对顺序按原磁带顺序保留。
例如 solution([[1.0, 100.5, 200], [3.0, 100.7, 150]], [[2.0, 100.6, 50], [3.0, 100.8, 75]], "V1", "V2") 应返回 [[1.0, 100.5, 200, "V1"], [2.0, 100.6, 50, "V2"], [3.0, 100.7, 150, "V1"], [3.0, 100.8, 75, "V2"]]。可以看到 t=3.0 同时出现在两条磁带,tape_a 的那一条排前——这一约定让“同时刻”的输出是确定性的。
由于两条磁带各可达 20 万行,线性扫描的两指针合并是这里的标准答案:O(n + m) 时间、O(n + m) 输出。
约束条件
- 0 ≤ len(tape_a), len(tape_b) ≤ 200000
- tape_a 与 tape_b 各自都按时间戳升序排列;同一磁带内允许时间戳并列,并列时保持原相对顺序
- tape_a[k] 形如 [timestamp, price, qty]:timestamp 是浮点秒(可正可负,绝对值 ≤ 1e12),price 是正浮点数,qty 是正整数
- venue_a 和 venue_b 是非空字符串场所标签(例如 "V1"、"V2"),允许相同(极少见,但题面不禁止)
- 返回一个列表,元素形如 [timestamp, price, qty, venue]:整体按 timestamp 升序;当两条磁带的队首时间戳相同时 tape_a 优先
样例
Case 1 · example from statement
输入: [[[1,100.5,200],[3,100.7,150]],[[2,100.6,50],[3,100.8,75]],"V1","V2"]
期望: [[1,100.5,200,"V1"],[2,100.6,50,"V2"],[3,100.7,150,"V1"],[3,100.8,75,"V2"]]
t=1.0 来自 V1,t=2.0 来自 V2,t=3.0 同时出现在两边——按 A 优先约定,V1 的那一条排前。
Case 2 · fully interleaved with no ties
输入: [[[0.1,50,10],[0.3,50.1,20],[0.5,50.2,30]],[[0.2,60,5],[0.4,60.1,15],[0.6,60.2,25]],"V1","V2"]
期望: [[0.1,50,10,"V1"],[0.2,60,5,"V2"],[0.3,50.1,20,"V1"],[0.4,60.1,15,"V2"],[0.5,50.2,30,"V1"],[0.6,60.2,25,"V2"]]
两条磁带的时间戳完全交错,合并后呈 V1-V2-V1-V2-V1-V2 的整齐穿插。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · example from statement
输入: [[[1,100.5,200],[3,100.7,150]],[[2,100.6,50],[3,100.8,75]],"V1","V2"]
期望: [[1,100.5,200,"V1"],[2,100.6,50,"V2"],[3,100.7,150,"V1"],[3,100.8,75,"V2"]]
t=1.0 来自 V1,t=2.0 来自 V2,t=3.0 同时出现在两边——按 A 优先约定,V1 的那一条排前。
Case 2 · fully interleaved with no ties
输入: [[[0.1,50,10],[0.3,50.1,20],[0.5,50.2,30]],[[0.2,60,5],[0.4,60.1,15],[0.6,60.2,25]],"V1","V2"]
期望: [[0.1,50,10,"V1"],[0.2,60,5,"V2"],[0.3,50.1,20,"V1"],[0.4,60.1,15,"V2"],[0.5,50.2,30,"V1"],[0.6,60.2,25,"V2"]]
两条磁带的时间戳完全交错,合并后呈 V1-V2-V1-V2-V1-V2 的整齐穿插。