题目描述
给定一个区间的集合 intervals ，其中 intervals[i] = [start_i, end_i] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
解题思路
本题为贪心算法的一个典型应用问题。解题的核心在于，要选出尽可能所的不重叠的区间，那就意味着咱们要选出的每个区间应该要尽可能窄。
考虑两个区间$[a_1, b_1]$和 $[a_2, b_2]$， 我们假设$b_1 \le b_2$, 分情况讨论：
- 如果$b_1 \le a_2$，那么我们可以知道，第二个区间整体是在第一个区间的右侧，两个区间可以同时存在
- 如果$b_1 > a_2$，这时候，第二个区间的起点可能在第一个区间中，或者完全覆盖了第一个区间。无论是哪种情况，都意味着第二个区间比第一个“长”。考虑咱们题目要求，要去掉尽可能少的区间实现区间不重叠，那么很自然要把长的空间去掉。这也是本题“贪心”的来源。
代码
分析完毕，咱们直接上代码。使用Python实现。
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
# 按照区间端点对区间进行排序
intervals.sort(key=lambda x: x[1])
lni = len(intervals)
# 边界情况，如果只有一个区间，直接返回，因为不需要任何操作
if lni == 1:
return 0
i = 0
res = 0
while i < len(intervals):
# 对每个区间，往前搜索可能重叠的区间
# 因为咱们已经对区间排序过，因此只需要判断每个区间的起点就可以
bi = intervals[i][1]
j = i + 1
while j < lni:
# 判断区间起点是否重叠，重叠则干掉
if intervals[j][0] < bi:
res += 1
j += 1
else:
break
# 注意循环退出条件：我们找到了下一个完全不重叠的区间
# 因此，用j更新i，中间那些区间已经被干掉
i = j
return res
运行结果
Accepted
58/58 cases passed (224 ms)
Your runtime beats 59.21 % of python3 submissions
Your memory usage beats 34.24 % of python3 submissions (39.2 MB)
