单会话子单调度:FIX 重配间隔下的最大不重叠窗口
Single-Session Child-Order Scheduling with FIX Reconfigure Gap
开始编码实现 solution(start_ms: list[int], end_ms: list[int], switch_cost_ms: int) -> int。两条平行数组描述了在某单一交易场所上的 N 个候选子单执行窗口:第 i 个窗口为 [start_ms[i], end_ms[i]),且 start_ms[i] < end_ms[i]。交易机器人在同一时间只能挂一笔子单,且每两笔连续子单之间需要 switch_cost_ms 毫秒的固定重配延迟(FIX 会话重定向所需的握手时间)。返回机器人最多能选出多少个窗口,使得所选子集互不重叠,并且任意相邻两个被选窗口满足 next.start_ms >= prev.end_ms + switch_cost_ms。
空输入(N == 0)返回 0。退化窗口(start_ms[i] >= end_ms[i])下的行为未定义——调用方负责保证窗口合法。switch_cost_ms == 0 时退化为经典活动选择基线;switch_cost_ms > 0 时是其严格推广,因为同一条"按 end 升序贪心"在这两种情形下都最优,尽管最优选择集合本身会改变。
例
solution([0, 100, 250, 280], [80, 200, 400, 350], 50) 返回 2。按 end_ms 升序排序后是 [(80, 0), (200, 100), (350, 280), (400, 250)]。先接受 (80, 0)(last_end = 80);下一个被接受的窗口需要 start >= 80 + 50 = 130,(200, 100) 的 start = 100 不达标,跳过;(350, 280) 的 start = 280 达标,接受(last_end = 350);最后一档 (400, 250) 的 start = 250 不到 350 + 50 = 400,跳过。一共接受 2 个。如果把 switch_cost_ms 改成 0,同样的输入会返回 3——这正是间隔参数会改变最优解的典型场景。
实现细节由 stubs/stub.py 提供。
实践背景
"单一 FIX 会话、同一时间只挂一笔子单"是小型算法执行机器人的标准结构:每个候选 [start_ms, end_ms) 都是上游信号层交给执行层的"可行窗口"——目标微观结构机制、报价稳定区间、或场所失衡口袋——而券商会话级别的重配延迟(FIX 上切换活跃合约、换 auth 标签的目标子账号、或等待限流令牌桶恢复)是交易员无法绕开的硬常数。"最大可选窗口数"给出的是"机器人在今天这一交易日里最多能落地多少个互不撕裂的切片"的上界;规划层会在切片优化器跑起来之前用它做一次可行性卡点。switch_cost_ms = 0 是没有握手开销的乐观基线;正的 switch_cost_ms 才是真实情形——多一毫秒的子单间隔就可能让排程从 N 个窗口掉到 N-1 或 N-2 个。
约束条件
- 0 <= N <= 5000,其中 N == len(start_ms) == len(end_ms);空输入返回 0
- 0 <= start_ms[i] < end_ms[i] <= 10^9(每个窗口长度严格为正);若任意 start_ms[i] >= end_ms[i](退化窗口)则行为未定义,调用方负责保证输入合法
- 0 <= switch_cost_ms <= 10^9(非负整数 FIX 会话重配延迟)
- switch_cost_ms == 0 时退化为经典活动选择问题(LC435/646 基线);switch_cost_ms > 0 时最优选择集合发生非平凡变化,但同一条按 end 升序的贪心仍然最优
- 输出为可行的最大窗口数:所选子集不重叠且任意相邻一对满足 next.start_ms >= prev.end_ms + switch_cost_ms
样例
Case 1 · statement-example: 4 windows with 50ms switch gap accept 2
输入: [[0,100,250,280],[80,200,400,350],50]
期望: 2
按 end_ms 升序:(80,0),(200,100),(350,280),(400,250);接受 (80,0),下一接受需 start>=130;(200,100) 不满足;(350,280) 满足,接受;(400,250) start=250<400,跳过。共 2 个。
Case 2 · visible: switch_cost=0 reduces to classical activity selection
输入: [[1,2,3,3],[3,4,5,6],0]
期望: 2
switch_cost=0 时退化为经典 LC435 不重叠区间选择;按 end 升序贪心可选 2 个。
Case 3 · visible: empty input returns 0
输入: [[],[],100]
期望: 0
N=0 直接返回 0,不查 switch_cost。
Case 4 · visible: switch_cost=1 forbids touching boundary
输入: [[0,5],[5,10],1]
期望: 1
两窗在 t=5 接边但 switch_cost=1 要求 next.start>=prev.end+1=6;不可同时选,最多 1 个。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: 4 windows with 50ms switch gap accept 2
输入: [[0,100,250,280],[80,200,400,350],50]
期望: 2
按 end_ms 升序:(80,0),(200,100),(350,280),(400,250);接受 (80,0),下一接受需 start>=130;(200,100) 不满足;(350,280) 满足,接受;(400,250) start=250<400,跳过。共 2 个。
Case 2 · visible: switch_cost=0 reduces to classical activity selection
输入: [[1,2,3,3],[3,4,5,6],0]
期望: 2
switch_cost=0 时退化为经典 LC435 不重叠区间选择;按 end 升序贪心可选 2 个。
Case 3 · visible: empty input returns 0
输入: [[],[],100]
期望: 0
N=0 直接返回 0,不查 switch_cost。
Case 4 · visible: switch_cost=1 forbids touching boundary
输入: [[0,5],[5,10],1]
期望: 1
两窗在 t=5 接边但 switch_cost=1 要求 next.start>=prev.end+1=6;不可同时选,最多 1 个。