Leetcode Link: 435. 无重叠区间 - 力扣（LeetCode）
题目
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。
解法一
思路：贪心，贪心的点在于：如果相邻的两个范围重叠，则必需去掉一个。找不到反例
这题有点像用最少数量的箭引爆气球，肯定需要先排序 为了方便，我们对两个关键字进行排序。
对于相邻的区间，有如下两种情况
- 前一个不包含后一个，但是重叠
- 前一个包含后一个（因为排序了，不可能有后一个包含前一个）
显然，对于 (1)，逐个遍历遇到重叠的，需要去掉后一个，即蓝色 对于 (2)，显然不能去掉蓝色(即下一个)，因为可能蓝色的下一个也在红色内，但是不和蓝色重叠。这样的话必需去掉红色
综上，两种情况，分类讨论，开始贪心
题解：
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: (x[0], x[1]))
cover = intervals[0]
res = 0
# 分类讨论移除相邻有重叠的区间
for val in intervals[1:]:
if cover[1] > val[1]: # 情况(2)
res += 1
cover = val
elif cover[1] > val[0]: # 情况(1)
res += 1
else:
cover = val
return res复习时采用了 naive 的想法，会超时 即真的去删除 (pop) 元素
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: (x[0], x[1]))
i=res = 0
# 分类讨论移除相邻有重叠的区间
while(i<len(intervals)-1):
head1, cover1 = intervals[i][0], intervals[i][1]
head2, cover2 = intervals[i+1][0], intervals[i+1][1]
if cover1 > cover2:
res += 1
i += 1
elif cover1 > head2:
res += 1
intervals.pop(i+1)
else:
i += 1
return res