代码与动画 INTERVAL SCHEDULING · GREEDY
区间调度.
优先选择结束最早的区间，求最多互不重叠的区间集合。
时间 O(n log n)扫描 O(n)最大化区间数量
原理与执行逻辑
按结束时间升序选择区间，每次保留与已选区间兼容且结束最早的候选。较早结束为后续留下更多可用时间，可最大化区间数量。
执行步骤
- 按区间终点排序。
- 以负无穷初始化上次选择的终点 end。
- 当前起点不小于 end 时选择该区间，并更新 end。
- 跳过发生重叠的区间，扫描结束后返回选中集合。
关键理解
当前问题最大化数量，区间没有权重。最优方案的首个区间可替换成结束最早者且不减少后续选择；起点等于上一终点时允许衔接。
简短示例
[1,4]、[3,5]、[4,6] 按结束时间扫描，选择 [1,4] 后跳过 [3,5]，再选择 [4,6]，共 2 个。
代码与执行动画
STEP 0 / 13function schedule(intervals) { const sorted = [...intervals].sort((a, b) => a[1] - b[1]); const result = []; let end = -Infinity; for (const interval of sorted) { if (interval[0] >= end) { result.push(interval); end = interval[1]; } } return result;}当前数据正在操作已访问 / 命中标记 / 指针
0
按结束时间排序
以结束时间升序扫描区间。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
区间调度的操作规则
按结束时间排序；一个区间的起点等于上一选择区间的终点时可继续选择。本问题不包含权重。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目435. 无重叠区间打开题目
最多保留互不重叠区间后，用区间总数减去保留数量。