买价跨越邻近卖价的跨磁带路由质量告警计数
Cross-Tape Buy-Above-Sell Routing-Quality Alert Count
开始编码某交易员的成交质量看板把一个标的当天的 BUY 磁带与 SELL 磁带送进来,要找一类特定的路由质量告警:任意 (i, j) 对,使得买单 i 与卖单 j 时间相差不超过 tol_ms 毫秒,且买单成交价不低于卖单成交价。这种对意味着智能路由本可以把买单与近时刻的卖单撮在一起、给买方拿到不更差的价格;这种"跨越事件"的总条数就是当天的路由低效得分。请实现 solution(ts_buy: list[int], px_buy: list[float], ts_sell: list[int], px_sell: list[float], tol_ms: int) -> int,返回满足以下条件的 (i, j) 对数:
|ts_buy[i] - ts_sell[j]| <= tol_ms AND px_buy[i] >= px_sell[j]ts_buy 与 ts_sell 是非递减整数毫秒时间戳数组;px_buy 与 px_sell 是平行的正浮点数价格数组。配对计数语义——每个满足两条件的 (i, j) 各贡献一次。两路时间戳预排序后,下界 ts_buy[i] - tol_ms 与上界 ts_buy[i] + tol_ms 在 i 上都非递减,所以两个卖侧指针 j_lo 与 j_hi 随 i 推进永不回退;指针推进的均摊开销是 O(B + S),再加上内层价格跨越判定的 O(total_pairs_in_window)。
边界情形:
- 若
len(ts_buy) == 0或len(ts_sell) == 0返回 0。 tol_ms == 0退化为「同时刻配对、买价不低于卖价」的计数;同一份代码仍然成立,因为窗口塌缩为一个点。- 若所有买价都低于所有卖价则计数为 0;若
tol_ms大到覆盖所有对、且每个买价不低于每个卖价,则计数为B * S。
例
ts_buy = [10, 20, 30, 40]
px_buy = [101.0, 102.0, 99.5, 100.0]
ts_sell = [11, 22, 31, 50]
px_sell = [100.0, 103.0, 99.0, 100.0]
tol_ms = 2solution(ts_buy, px_buy, ts_sell, px_sell, tol_ms) 返回 2。对 (i=0, j=0):|10 - 11| = 1 <= 2 且 101.0 >= 100.0,计入。对 (i=1, j=1):|20 - 22| = 2 <= 2 但 102.0 < 103.0,价格不跨越。对 (i=2, j=2):|30 - 31| = 1 <= 2 且 99.5 >= 99.0,计入。对 (i=3, j=3):|40 - 50| = 10 > 2,时间不在窗内。其他对均不在容差窗口内,因此总数为 2。
实践背景
跨磁带「买价跨越近时刻卖价」对计数是 trading ops 在每日磁带上跑的一类路由质量告警。跨越数偏高意味着智能路由把 BUY 子单先打了出去、对家的 SELL 印还没出清——买方付了点差,而桌内自家的 SELL 侧本可以把这份单子吃掉。指标按日聚合,对当天两侧磁带各扫一次。生产磁带动辄几千万条成交,所以两端线性的双指针形状(在合理的 tol_ms 下窗口经验上很小)才是把日报压到分钟级的关键;朴素的 O(B * S) 双重循环跑不动。与同侧两路冗余 feed 的对账不同,这里把对端磁带配对、并加上价格跨越判定。
约束条件
- 0 ≤ B、S ≤ 5000,其中 B = len(ts_buy)、S = len(ts_sell)。另外 B + S ≤ 7500。算法应保持 O(B + S + total_pairs_in_window),从而在更大规模磁带上仍能在时限内完成。
- -1e9 ≤ ts_buy[i]、ts_sell[j] ≤ 1e9(整数毫秒);两数组均非递减(升序排序,单条磁带内允许重复时间戳)。
- 0.001 ≤ px_buy[i]、px_sell[j] ≤ 1e6(正浮点数)。len(px_buy) == len(ts_buy)、len(px_sell) == len(ts_sell)。
- 0 ≤ tol_ms ≤ 1e9。匹配窗口 `[ts_buy[i] - tol_ms, ts_buy[i] + tol_ms]` 两端均闭。
- 输出是 `[0, B*S]` 区间内的单一非负整数。配对计数语义——每个满足两条件的 `(i, j)` 都贡献 1 次计数;不是按买单存在性计数。
- 两个判定条件的等号都计入:`|ts_buy[i] - ts_sell[j]| == tol_ms` 仍在窗内,`px_buy[i] == px_sell[j]` 仍算跨越。
- 边界情形:B = 0 或 S = 0 返回 0;tol_ms = 0 退化为「同时刻、买价不低于卖价」的计数;若所有买价都低于所有卖价则计数为 0。
样例
Case 1 · statement-example: two crossed events at tol=2
输入: [[10,20,30,40],[101,102,99.5,100],[11,22,31,50],[100,103,99,100],2]
期望: 2
题面例:tol=2 时仅 (i=0,j=0) 在 |10-11|=1 内且 101.0>=100.0、(i=2,j=2) 在 |30-31|=1 内且 99.5>=99.0 满足两条件;(i=1,j=1) 时间近但 102.0<103.0;i=3 没有 sell 落在窗口内。
Case 2 · typical: tol_ms=0 collapses to exact-timestamp price-cross check
输入: [[5,10,15,20,25],[100.5,101,99,102.5,98],[5,10,15,20,30],[99.5,101.5,99,102,99],0]
期望: 3
tol=0 时窗口塌缩为同时刻;ts=5 时 100.5>=99.5 计 1,ts=15 时 99.0>=99.0 计 1,ts=20 时 102.5>=102.0 计 1;ts=10 时 101.0<101.5 不计;ts=25 没有 sell。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: two crossed events at tol=2
输入: [[10,20,30,40],[101,102,99.5,100],[11,22,31,50],[100,103,99,100],2]
期望: 2
题面例:tol=2 时仅 (i=0,j=0) 在 |10-11|=1 内且 101.0>=100.0、(i=2,j=2) 在 |30-31|=1 内且 99.5>=99.0 满足两条件;(i=1,j=1) 时间近但 102.0<103.0;i=3 没有 sell 落在窗口内。
Case 2 · typical: tol_ms=0 collapses to exact-timestamp price-cross check
输入: [[5,10,15,20,25],[100.5,101,99,102.5,98],[5,10,15,20,30],[99.5,101.5,99,102,99],0]
期望: 3
tol=0 时窗口塌缩为同时刻;ts=5 时 100.5>=99.5 计 1,ts=15 时 99.0>=99.0 计 1,ts=20 时 102.5>=102.0 计 1;ts=10 时 101.0<101.5 不计;ts=25 没有 sell。