← 返回编程题库
coding-max-non-overlap-trade-windows简单免费版2000ms未尝试

最多不重叠交易时间窗

Max Non-Overlapping Trade Windows

开始编码

执行控制台桌面接到当日的候选 交易时间窗 列表——每个窗口 [start, end) 是半开的时间区间(左闭右开,单位为自纪元以来的秒数),在该窗口内某个大宗交易或合规审计可以合法发起。很多窗口在时间上重叠,但这条执行通道一次只能跑一个窗口,不能有时间冲突。问题是:今天最多能排进几个窗口?等价的算法表述是:给定一组区间,最多能挑出多少两两不相交的?

请实现 solution(windows: list[list[int]]) -> int,返回最大数量。每个 windows[k] = [start, end] 满足 start ≤ end。两个窗口 [a, b)[c, d) 相交当且仅当交集非空,即 a < d 且 c < b。在端点处相切(例如 [1, 5)[5, 10)不算相交(点 5 只属于第二个窗口),可同时选。退化的点区间(start == end)是空集,不与任何区间冲突。

示例solution([[1,5],[2,3],[3,8],[5,7],[7,10]]) 返回 3。按 end 升序排:[2,3),[1,5),[5,7),[3,8),[7,10)。贪心扫描:选 [2,3)(计数 1,末端 3);[1,5) 起点 1 < 3,跳过;选 [5,7)(计数 2,末端 7);[3,8) 起点 3 < 7,跳过;选 [7,10)(计数 3,末端 10)。solution([[0,10],[1,9],[2,8],[3,7]]) 返回 1——四个区间都包含 [3,7),两两相交,最多只能选一个。solution([[1,5],[5,10],[10,20]]) 返回 3——链条只在单点相切,半开语义下三个都可选。

经典算法是 区间调度极大化:按 end 升序排序,贪心地选择下一个 start ≥ 上一个选中区间 end 的窗口。交换论证:在所有最大基数的解里,一定存在一个解的「第一个区间」是全局结束最早的那个;把任何其他「第一选择」替换成它都不会减少数量,因为它在时间轴上至少同样早地释放资源。时间复杂度 O(n log n),瓶颈在排序,扫描本身只 O(n)。这套贪心是批处理调度、审计窗口安排、会议室预订等「在单一资源上塞下尽可能多互不冲突任务」类问题的通用解。

约束条件

  • 0 ≤ len(windows) ≤ 10⁴
  • 每个 `windows[k] = [start, end]` 满足 `0 ≤ start ≤ end ≤ 10⁹`(整数时间戳,例如自纪元以来的秒数)
  • 区间为半开 `[start, end)`——单点相切不算重叠
  • 允许退化的点区间(`start == end`),视作空集,与任何区间都不相交
  • 返回 `int` 类型,精确比较,不涉及浮点容差

样例

Case 1 · mixed — three picked from five

输入: [[[1,5],[2,3],[3,8],[5,7],[7,10]]]

期望: 3

按结束时间升序:[2,3),[1,5),[5,7),[3,8),[7,10)。贪心依次考察:选 [2,3) → 上一结束 3;[1,5) 起点 1<3 跳过;[5,7) 起点 5≥3 选;[3,8) 起点 3<7 跳过;[7,10) 起点 7≥7 选。共 3 个。

Case 2 · all overlap a common point — pick one

输入: [[[0,10],[1,9],[2,8],[3,7]]]

期望: 1

四个区间都包含 [3,7),两两相交。最多只能挑 1 个。

Case 3 · three fully disjoint windows

输入: [[[0,2],[5,7],[10,12]]]

期望: 3

三个区间互不相交,全部可选,答案 3。

Case 4 · point-touch — half-open semantics allow chaining

输入: [[[1,5],[5,10],[10,20]]]

期望: 3

区间是 [start, end),所以 [1,5) 和 [5,10) 在 5 处仅相切、不相交(5 不属于第一个区间),可以同时选;同理 [5,10) 与 [10,20) 也合法。共 3 个。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · mixed — three picked from five

输入: [[[1,5],[2,3],[3,8],[5,7],[7,10]]]

期望: 3

按结束时间升序:[2,3),[1,5),[5,7),[3,8),[7,10)。贪心依次考察:选 [2,3) → 上一结束 3;[1,5) 起点 1<3 跳过;[5,7) 起点 5≥3 选;[3,8) 起点 3<7 跳过;[7,10) 起点 7≥7 选。共 3 个。

Case 2 · all overlap a common point — pick one

输入: [[[0,10],[1,9],[2,8],[3,7]]]

期望: 1

四个区间都包含 [3,7),两两相交。最多只能挑 1 个。

Case 3 · three fully disjoint windows

输入: [[[0,2],[5,7],[10,12]]]

期望: 3

三个区间互不相交,全部可选,答案 3。

Case 4 · point-touch — half-open semantics allow chaining

输入: [[[1,5],[5,10],[10,20]]]

期望: 3

区间是 [start, end),所以 [1,5) 和 [5,10) 在 5 处仅相切、不相交(5 不属于第一个区间),可以同时选;同理 [5,10) 与 [10,20) 也合法。共 3 个。