← 返回编程题库
coding-max-throughput-child-orders-with-windows中等免费版2000ms未尝试

单会话最大子单吞吐:每单独立时长与 FIX 重配间隔

Maximum Child-Order Throughput With Per-Order Durations And A FIX-Session Gap

开始编码

实现 solution(latest_finish_ms: list[int], duration_ms: list[int], min_gap_ms: int) -> int。两条平行数组描述了在某单一交易场所上的 N 个候选子单:第 i 单的处理时长固定为 duration_ms[i],必须在绝对截止时间 latest_finish_ms[i] 之前完成(毫秒时间轴,所有单从时间 0 起即可调度)。交易机器人在同一时间只能挂一笔子单,且每两笔连续子单之间需要 min_gap_ms 毫秒的固定重配延迟(FIX 会话握手)。返回机器人最多能接受多少单,使得每个被接受单都在自己的 latest_finish_ms 之前完成,并且任意相邻两个被接受单满足 next.start >= prev.end + min_gap_ms

空输入(N == 0)返回 0。每个单独立可行(duration_ms[i] <= latest_finish_ms[i]);若有 duration_ms[i] > latest_finish_ms[i] 则行为未定义。min_gap_ms == 0 时退化为经典的 1||sum U_j Moore-Hodgson 基线;min_gap_ms > 0 时是其严格推广,因为同一条堆逐出算法在这两种情形下都最优,尽管最优选择集合本身会改变。

solution([10, 11, 12, 13], [10, 2, 2, 2], 0) 返回 3。朴素的 deadline 扫描会先接受时长 10 的长单(恰好赶在 deadline 10 前),然后 deadline 11 的时长 2 单放不下(累计 12 > 11,跳过),deadline 12 的时长 2 单恰好放下(累计 12 <= 12,接受),deadline 13 的时长 2 单又放不下(累计 14 > 13)——扫描返回 2。Moore-Hodgson 的逐出步骤会把那个长单逐出:堆里压入四单后逐出时长 10,剩下三个时长 2 的单完成时间分别为 246,都在各自 deadline 之内。最终接受 3 个。把 min_gap_ms 改成 1 时同输入仍返回 3(最终累计 2 + 1 + 2 + 1 + 2 = 8,依旧远低于 deadline)。

实现细节由 stubs/stub.py 提供。

实践背景

"单 FIX 会话、同一时间只挂一笔子单"是算法执行机器人的标准结构:每个候选单都有一个固定的往返处理时长(duration_ms[i],由切片大小、市场深度、场所 ack 延迟决定)和一个硬性的"必须完成"截止时间(latest_finish_ms[i],由父策略的切片窗口或合规上报截止决定)。会话级别的重配间隔(min_gap_ms)是券商 FIX 上切换合约、刷新 auth 标签子账号、或等待限流令牌桶恢复所需的时间。"最大吞吐"给出的是"单 FIX 会话在今天这一交易日里最多能合规完成多少子单"的上界;规划层会在切片器投入资源之前用它做一次可行性卡点。Moore-Hodgson 的逐出动作正是它和课本式活动选择扫描的本质区别——当某个长单会卡住后续多个短单时,逐出步骤会选择更多的短单留下,对应生产调度器中"deadline 紧迫时优先快单"的启发式。

约束条件

  • 0 <= N <= 5000,其中 N == len(latest_finish_ms) == len(duration_ms);两数组等长;空输入返回 0
  • 0 <= duration_ms[i] <= latest_finish_ms[i] <= 10^9(保证每个单**独立**可行——第 i 单单独执行时一定能在 [0, latest_finish_ms[i]] 内完成,因为 duration_ms[i] <= latest_finish_ms[i]);若任意 duration_ms[i] > latest_finish_ms[i],行为未定义
  • 0 <= min_gap_ms <= 10^9(非负整数 FIX 会话重配延迟,仅作用于相邻被接受单之间,不作用于第一个单之前)
  • min_gap_ms == 0 时退化为经典 `1||sum U_j` 的 Moore-Hodgson 基线;min_gap_ms > 0 时最优选择集合发生非平凡变化,但同一条堆逐出算法仍然最优
  • 输出为可行的最大被接受单数:所选子集顺序排程在单一场所上,每个被接受单都在其 latest_finish_ms 之前完成,且任意相邻一对满足 next.start >= prev.end + min_gap_ms

样例

Case 1 · statement-example: long blocker evicted, 3 short survivors

输入: [[10,11,12,13],[10,2,2,2],0]

期望: 3

Moore-Hodgson 逐出时长 10 的长单,留下三个时长 2 的短单,完成时间为 2、4、6,都在 deadline 内。简单扫描会被长单卡住只剩 2 个。

Case 2 · statement-example: gap=1, same Moore-Hodgson outcome

输入: [[10,11,12,13],[10,2,2,2],1]

期望: 3

gap=1 下三个短单累计耗费 2+1+2+1+2=8,仍远低于最大 deadline 13,结果仍为 3。

Case 3 · empty: zero candidates returns 0

输入: [[],[],100]

期望: 0

空输入直接返回 0。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · statement-example: long blocker evicted, 3 short survivors

输入: [[10,11,12,13],[10,2,2,2],0]

期望: 3

Moore-Hodgson 逐出时长 10 的长单,留下三个时长 2 的短单,完成时间为 2、4、6,都在 deadline 内。简单扫描会被长单卡住只剩 2 个。

Case 2 · statement-example: gap=1, same Moore-Hodgson outcome

输入: [[10,11,12,13],[10,2,2,2],1]

期望: 3

gap=1 下三个短单累计耗费 2+1+2+1+2=8,仍远低于最大 deadline 13,结果仍为 3。

Case 3 · empty: zero candidates returns 0

输入: [[],[],100]

期望: 0

空输入直接返回 0。