最多不重叠交易时间窗
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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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 个。