难度: Medium
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= starti < endi <= 5 * 104运行时间: 126 ms
内存: 46.9 MB
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals = sorted(intervals, key=lambda x: x[1])
ans = 1
right =intervals[0][1]
for i in intervals[1:]:
if i[0]< right:
continue
else:
right = i[1]
ans += 1
return len(intervals)-ans
该题解的思路是贪心算法。首先将区间按照结束时间从小到大排序。然后从第一个区间开始，初始化一个计数器 ans 为1，表示至少有一个不重叠的区间。同时用一个变量 right 记录当前选择区间的结束时间。遍历后面的区间，如果当前区间的开始时间小于 right，说明有重叠，跳过该区间；否则，将 right 更新为当前区间的结束时间，ans 加1。最后用区间总数减去 ans，即为需要移除的最小区间数。
时间复杂度: O(nlogn)
空间复杂度: O(n)
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
# 按照区间结束时间从小到大排序
intervals = sorted(intervals, key=lambda x: x[1])
# 初始化计数器和右边界
ans = 1
right = intervals[0][1]
# 遍历排序后的区间
for i in intervals[1:]:
# 如果当前区间的开始时间小于右边界，说明有重叠，跳过
if i[0] < right:
continue
# 否则，更新右边界和计数器
else:
right = i[1]
ans += 1
# 返回需要移除的区间数
return len(intervals) - ans
在贪心选择法中，初始化 ans 为 1 是基于算法从第一个区间开始选择的假设。这表明在开始时，至少有一个区间已被选为非重叠区间。因此，这确实意味着至少有一个区间不需要移除。这种初始化方法是为了简化计数逻辑，因为第一个区间自然不与任何前面的区间重叠。