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

最少需移除的再平衡时间窗

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

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

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

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