节流窗口合规回放:最少需撤单次数
Throttle-Window Compliance Replay: Minimum Order Cancels
开始编码实现 solution(times: list[float], W: float, K: int) -> int。一台订单路由器在(已按升序排列的)时间戳 times(单位:秒)向某交易场所发出订单。该场所启用节流:任意一个闭的 W 秒滚动窗口内,存活的订单数最多为 K。返回最少需要撤掉的订单数,使得在剩余时间戳上,每个 W 秒滚动窗口内的存活订单都不超过 K。
输入为空时返回 0;若整段时间戳本身就满足节流约束(每个 W 秒窗口都不超过 K),同样返回 0。窗口两端均为闭区间:位于"窗口起点 + W"位置处的时间戳仍然算在该窗口内。等值时间戳视为同一时刻并发,全部计入同一窗口。
例:solution([0.0, 1.0, 2.0, 3.0], 2.0, 2) 返回 1。以 0.0 为起点的前向窗口 [0.0, 2.0] 内有三个时间戳,需要撤掉一笔;贪心撤掉 times[2] = 2.0(违规窗口内最晚的那一笔),剩下 {0.0, 1.0, 3.0} 在所有闭 2 秒窗口内的存活数都不超过 2。
朴素的 O(N^2) 解法(对每个起点重新数一次窗口)在较大的隐藏用例上会超时;预期解法是一次自左向右的双指针线性扫描:每来一笔新订单,先剔除掉时间落在 [t - W, t] 区间外的存活订单,然后判断如果把这笔加入是否会让窗口内的存活数超过 K——超过则撤掉这一笔。这一贪心可证为最优:撤违规窗口内"最晚"的那一笔不会让任何更早的窗口变差,且最大化缓解了后续窗口。
实现细节由 stubs/stub.py 提供。
实践背景
交易场所的合规网关通常会对单客户端在滚动时间窗内的活跃订单数设上限——这是对失控循环、参数误填、热路径压测等场景的一道粗粒度防线,避免把撮合引擎打挂。运维或合规团队在做事后回放(成交对账、节流参数 what-if、下一次上线前的调参)时,"为了严格满足节流约束,至少要撤掉多少笔?"这个问题既给出了监管视角下的最差情形,也给出了节流真上线后吞吐损耗的一个上界。贪心"撤违规窗口内最晚的一笔"恰好就是大多数场所线上跑的实时节流逻辑,所以离线回放出来的数和线上实际被拦截的笔数应当吻合(前提是上线参数与回放参数一致)。
约束条件
- 0 <= N <= 200000,其中 N 为 solution(times, W, K) 的输入长度
- times 按非降序排列;允许等值(视为同一时刻并发)
- W > 0(严格为正的浮点秒数);1 <= K <= N(当 N >= 1 时)
- 窗口在两端均为闭区间——位于 `t + W` 处的存活订单仍然算在起点为 t 的窗口内
- 输出为非负整数,使用精确比对
样例
Case 1 · statement-example: 4 ts spaced 1s, W=2 K=2 needs 1 cancel
输入: [[0,1,2,3],2,2]
期望: 1
窗口 [0,2] 含 3 个时间戳超过 K=2,撤掉最晚的 times[2]=2.0;剩余 {0,1,3} 在所有 2 秒窗口内均 <= 2。
Case 2 · visible: already compliant, no cancels
输入: [[0,5,10,15],4,1]
期望: 0
任意 4 秒窗口最多包含 1 个时间戳,已经满足 K=1,无需撤单。
Case 3 · visible: closed-window boundary - timestamp at t+W counts as inside
输入: [[0,2,4],2,1]
期望: 1
窗口 [0,2] 闭区间含 0.0 与 2.0 共 2 个超过 K=1,撤掉 times[1]=2.0;之后 [2,4] 也只剩 4.0 一个。最终撤 1 笔。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: 4 ts spaced 1s, W=2 K=2 needs 1 cancel
输入: [[0,1,2,3],2,2]
期望: 1
窗口 [0,2] 含 3 个时间戳超过 K=2,撤掉最晚的 times[2]=2.0;剩余 {0,1,3} 在所有 2 秒窗口内均 <= 2。
Case 2 · visible: already compliant, no cancels
输入: [[0,5,10,15],4,1]
期望: 0
任意 4 秒窗口最多包含 1 个时间戳,已经满足 K=1,无需撤单。
Case 3 · visible: closed-window boundary - timestamp at t+W counts as inside
输入: [[0,2,4],2,1]
期望: 1
窗口 [0,2] 闭区间含 0.0 与 2.0 共 2 个超过 K=1,撤掉 times[1]=2.0;之后 [2,4] 也只剩 4.0 一个。最终撤 1 笔。