用各自的时钟偏移把 K 路成交磁带对齐到全局时钟
Realign K Trade Tapes to a Global Clock with Per-Tape Offsets
开始编码交易台需要把来自 K 个执行场所的成交磁带整合到一条参考时钟上。每个场所 k(即 tapes 中从 0 起的下标)落下一条按 local 时间戳非降序排列的整数列表 tapes[k],每个元素都是该场所的一笔独立成交事件。每个场所运行各自的本地时钟,与交易台参考时钟之间存在一个已知的固定偏移 offsets[k]:第 k 条磁带第 i 条事件的 GLOBAL 时间戳为 tapes[k][i] + offsets[k]。
任何跨场所的统计——NBBO 切片、合并成交磁带上的 VWAP、跨场所订单流相关性——都要先有一个 按全局时钟排序的统一事件视图,并把每行事件的来源 tape_id 一并保留,下游才能把每条事件追溯回其场所。
请实现 solution(tapes: list[list[int]], offsets: list[int]) -> list[list[int]]。输出是一段 2 元素列表 [global_ts, tape_id],严格按 global 序排列:主键 global_ts 升序,次键 tape_id 升序。输出长度等于所有磁带的事件总数;若所有磁带都为空(或事件总数为 0),返回 []。
边界情况:
- 某条
tapes[k] == []是合法的,静默跳过、不贡献任何输出。 - 不同磁带的事件可能映射到相同的
global_ts;此时tape_id较小者先输出。 - 同一条磁带内部也可能有两条事件
global_ts相等(如重复 local 时间戳);此时按它们在该磁带中的输入顺序输出。
例
tapes = [[10, 30], [12, 18], [25]]
offsets = [5, 3, -10]每条磁带的 global 流分别是 tape 0 -> [15, 35]、tape 1 -> [15, 21]、tape 2 -> [15]。三条磁带的首事件都映射到 global_ts = 15,故按 tape_id 升序输出 (15, 0)、(15, 1)、(15, 2);其后是 tape 1 的 18 + 3 = 21,最后是 tape 0 的 30 + 5 = 35。solution(tapes, offsets) 返回:
[[15, 0], [15, 1], [15, 2], [21, 1], [35, 0]]实践背景
跨场所时钟对齐是合并磁带上一切分析的前置步骤。每个场所按各自的本地时钟给成交打戳,与交易台参考时钟之间存在一个由 drop-copy 心跳或对账报告测得的固定偏移。只有把事件按全局时钟重排后,下游所有任务——NBBO 重建、合并成交磁带上的 VWAP、跨场所订单流归因——才能在一张时间序正确的表上运行。若忽略 offsets 直接按 local 时间戳归并,凡正向偏移的场所都会被系统性置后,所有跨场所统计随之失真。
约束条件
- 0 <= K <= 64;0 <= 所有磁带事件总数 <= 5000。其中 K 即 len(tapes),且始终满足 len(offsets) == len(tapes)。
- 每条磁带的 local 时间戳按非降序预排序;offsets[k] 是有符号整数。
- -1e9 <= 每个 local 时间戳 <= 1e9;-1e9 <= 每个 offsets[k] <= 1e9。
- 第 k 条磁带第 i 条事件的 GLOBAL 时间戳为 `tapes[k][i] + offsets[k]`(整数运算,不存在浮点漂移)。
- 输出为 `list[list[int]]`,每行 `[global_ts, tape_id]`,严格按 global 序输出——主键 global_ts 升序,次键 tape_id 升序。
- 不同磁带两条事件 global_ts 相等时,tape_id 更小的先输出。
- 允许某条 `tapes[k] == []` 的空磁带;当事件总数为 0 时返回 `[]`,所有磁带为空时返回 `[]`。
样例
Case 1 · statement-example: three tapes with global ties resolved by tape_id
输入: [[[10,30],[12,18],[25]],[5,3,-10]]
期望: [[15,0],[15,1],[15,2],[21,1],[35,0]]
题面例题:tape 0 偏移=+5、tape 1 偏移=+3、tape 2 偏移=-10。三个磁带的首条事件全部映射到 global=15,因此先按 tape_id 升序输出 (15,0)、(15,1)、(15,2);之后 tape 1 的 18+3=21 紧随其后,最后 30+5=35。
Case 2 · typical: opposite-sign offsets reorder relative to local order
输入: [[[1,5,9],[50,60,70]],[100,50]]
期望: [[100,1],[101,0],[105,0],[109,0],[110,1],[120,1]]
两条磁带,offsets 大小不一:tape 0 整体被 +100 抬升、tape 1 被 +50 抬升。原本 tape 0 的 local=1 比 tape 1 的 local=50 早,但加上偏移后 tape 1 的 100 反而更早,输出顺序由 global 时钟决定。
Case 3 · typical: four tapes converge on same global ts, tape_id ascending
输入: [[[5],[3],[10],[-2]],[0,2,-5,7]]
期望: [[5,0],[5,1],[5,2],[5,3]]
四条磁带的唯一事件经各自偏移后全部映射到 global=5;并列时按 tape_id 升序输出,所以顺序是 (5,0)、(5,1)、(5,2)、(5,3)。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: three tapes with global ties resolved by tape_id
输入: [[[10,30],[12,18],[25]],[5,3,-10]]
期望: [[15,0],[15,1],[15,2],[21,1],[35,0]]
题面例题:tape 0 偏移=+5、tape 1 偏移=+3、tape 2 偏移=-10。三个磁带的首条事件全部映射到 global=15,因此先按 tape_id 升序输出 (15,0)、(15,1)、(15,2);之后 tape 1 的 18+3=21 紧随其后,最后 30+5=35。
Case 2 · typical: opposite-sign offsets reorder relative to local order
输入: [[[1,5,9],[50,60,70]],[100,50]]
期望: [[100,1],[101,0],[105,0],[109,0],[110,1],[120,1]]
两条磁带,offsets 大小不一:tape 0 整体被 +100 抬升、tape 1 被 +50 抬升。原本 tape 0 的 local=1 比 tape 1 的 local=50 早,但加上偏移后 tape 1 的 100 反而更早,输出顺序由 global 时钟决定。
Case 3 · typical: four tapes converge on same global ts, tape_id ascending
输入: [[[5],[3],[10],[-2]],[0,2,-5,7]]
期望: [[5,0],[5,1],[5,2],[5,3]]
四条磁带的唯一事件经各自偏移后全部映射到 global=5;并列时按 tape_id 升序输出,所以顺序是 (5,0)、(5,1)、(5,2)、(5,3)。