最少需移除的再平衡时间窗
Min Rebalance Windows To Remove
开始编码组合运营团队为当日排出一组候选 再平衡时间窗 ——每个窗口 [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]]) 返回 2。最大互不相交子集大小为 3([2,3), [5,7), [7,10)),故需移除 5 − 3 = 2 个(具体即 [1,5) 和 [3,8))。solution([[0,10],[1,9],[2,8],[3,7]]) 返回 3——四个区间都包含 [3,7),最多只能保留 1 个,其余 3 个必须移除。solution([[1,5],[5,10],[10,20]]) 返回 0——链条只在单点相切,半开语义下三个都可保留,无需移除。
经典算法是先对保留问题做 区间调度极大化,再做减法:按 end 升序排序,贪心地选择下一个 start ≥ 上一个被保留区间 end 的窗口,记保留个数为 K,返回 len(windows) − K。时间复杂度 O(n log n),瓶颈在排序。「最小移除数」框架在以下场景里更自然:输入是一份必要但相互冲突的候选窗口清单,运营关心的是「我得砍掉多少」而非「我能塞进几个」。两者互为对偶,但移除框架直接对应容量规划、审计窗口剪枝、以及任何「为满足单资源约束需要的最小取消数」的情境。
约束条件
- 0 ≤ len(windows) ≤ 10⁴
- 每个 `windows[k] = [start, end]` 满足 `0 ≤ start ≤ end ≤ 10⁹`(整数时间戳,例如自纪元以来的秒数)
- 区间为半开 `[start, end)`——单点相切不算重叠
- 允许退化的点区间(`start == end`),视作空集,与任何区间都不相交
- 返回 `int` 类型,精确比较,不涉及浮点容差
样例
Case 1 · mixed — two removed from five
输入: [[[1,5],[2,3],[3,8],[5,7],[7,10]]]
期望: 2
最大互不相交子集 [2,3),[5,7),[7,10) 大小为 3,故移除数为 5−3=2(具体即 [1,5) 与 [3,8))。
Case 2 · all overlap a common point — remove all but one
输入: [[[0,10],[1,9],[2,8],[3,7]]]
期望: 3
四个区间两两相交(都包含 [3,7)),最多保留 1 个,其余 3 个必须移除。
Case 3 · three fully disjoint windows — none removed
输入: [[[0,2],[5,7],[10,12]]]
期望: 0
三个区间互不相交,全部保留,移除数为 0。
Case 4 · point-touch chain — half-open keeps all
输入: [[[1,5],[5,10],[10,20]]]
期望: 0
链条仅在单点 5、10 处相切,半开语义下不算重叠,三者全部保留,移除数为 0。
Case 5 · sort-by-start trap — engulfing big interval
输入: [[[1,100],[2,3],[4,5],[6,7]]]
期望: 1
按起点排会先选 [1,100) 把后面三个全堵死。按结束时间贪心可保留 [2,3),[4,5),[6,7) 共 3 个,必须移除 [1,100) 这 1 个。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · mixed — two removed from five
输入: [[[1,5],[2,3],[3,8],[5,7],[7,10]]]
期望: 2
最大互不相交子集 [2,3),[5,7),[7,10) 大小为 3,故移除数为 5−3=2(具体即 [1,5) 与 [3,8))。
Case 2 · all overlap a common point — remove all but one
输入: [[[0,10],[1,9],[2,8],[3,7]]]
期望: 3
四个区间两两相交(都包含 [3,7)),最多保留 1 个,其余 3 个必须移除。
Case 3 · three fully disjoint windows — none removed
输入: [[[0,2],[5,7],[10,12]]]
期望: 0
三个区间互不相交,全部保留,移除数为 0。
Case 4 · point-touch chain — half-open keeps all
输入: [[[1,5],[5,10],[10,20]]]
期望: 0
链条仅在单点 5、10 处相切,半开语义下不算重叠,三者全部保留,移除数为 0。
Case 5 · sort-by-start trap — engulfing big interval
输入: [[[1,100],[2,3],[4,5],[6,7]]]
期望: 1
按起点排会先选 [1,100) 把后面三个全堵死。按结束时间贪心可保留 [2,3),[4,5),[6,7) 共 3 个,必须移除 [1,100) 这 1 个。