LC435
无重叠区间
区间 · 无重叠可视化:区间时间轴intervals=[[1,2],[2,3],[3,4],[1,3]] 最少移除使无重叠。
时间 O(n)空间 O(1)
题目1 / 9
题目与输入建立输入、目标与算法心智
贪心:优先保留结束最早的区间
正在加载算法场景...
当前发生了什么
intervals=[[1,2],[2,3],[3,4],[1,3]] 最少移除使无重叠。
机器状态
排序、prev end、移除计数。
为什么正确
按 end 排序贪心,能留则留(end 更小优先)。
不变量
按结束早的留更多空间。
面试怎么说
sort by end 贪心 O(n log n)。
人类输入
intervals=[[1,2],[2,3],[3,4],[1,3]] 最少移除使无重叠。
机制
按 end 排序贪心,能留则留(end 更小优先)。
机器状态
排序、prev end、移除计数。
可观察结果
最少移除 1。
不变量
- · 按结束早的留更多空间。
常见误区
- · 按 start 排序不是最优贪心。
迁移练习
- · LC452 气球
- · LC56 合并
面试怎么答
sort by end 贪心 O(n log n)。