无重叠区间
Non-overlapping Intervals
本机进度仅保存在当前浏览器
题目描述
给定一个区间的集合 intervals，其中 intervals[i] = [starti, endi]。返回需要移除区间的最小数量，使剩余区间互不重叠（端点相触不算重叠）。
示例：intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]，移除 [1, 3] 后无重叠，输出 1。
解题思路
- 等价转换：最小移除数 = 总数 - 最多能保留的互不重叠区间数，这是经典区间调度问题。
- 贪心策略：按右端点升序排列，每次选右端点最小的区间保留，给后面留出最大空间。
- 扫描时若当前区间左端点 >= 已保留区间的最大右端点则保留，否则计入移除。
参考实现
查看参考实现Python · 建议先自行作答
def eraseOverlapIntervals(intervals):
intervals.sort(key=lambda x: x[1])
keep = 0
end = float('-inf')
for start, e in intervals:
# 右端点最小者优先保留
if start >= end:
keep += 1
end = e
return len(intervals) - keep