← 返回编程题库
coding-max-nonoverlap-windows-with-switch-gap中等免费版2000ms未尝试

单会话子单调度: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 可见样例;服务端提交会运行可见样例和隐藏测试。

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

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

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 个。