Leetcode 435. 无重叠区间
1.题目描述
给定一个区间的集合
intervals，其中 intervals[i] = [ s t a r t i , e n d i ] [start_i, end_i] [starti,endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
- 1 <= intervals.length <= 10^5
- intervals[i].length == 2
- -5 * 1 0 4 10^4 104 <= starti < endi <= 5 * 1 0 4 10^4 104
2.思路分析
2.1 动态规划
题目的要求等价于「选出最多数量的区间，使得它们互不重叠」。
由于选出的区间互不重叠，因此我们可以将它们按照端点从小到大的顺序进行排序，并且无论我们按照左端点还是右端点进行排序，得到的结果都是唯一的。
先将所有的 n个区间按照左端点(或者右端点)从小到大进行排序，随后使用动态规划的方法求出区间数量的最大值。
设排完序后这 n 个区间的左右端点分别为 l 0 , ⋯ , l n − 1 l_0,⋯,l_n−1 l0,⋯,ln−1以及 r 0 , ⋯ , r n − 1 r_0,⋯,r_n−1 r0,⋯,rn−1
1.确定dp数组以及下标含义
- dp[i]:列表从0开始到位置i之间最多的无重叠区间的个数
2.确定递推公式
- dp[i] = max(dp[i].dp[j]+1),j是从i遍历到位置0遇到的第一个与i无重复区间的位置
- dp[i] = max(dp[i],dp[i-1])，找到从位置0到位置i中最多的无重叠区间
3.dp数组初始化
- dp初始化为1
4.确定遍历顺序
- 循环外层:i 循环内层:j(反向遍历)
5.举例推导dp数组
2.2 贪心
Q: 选择哪一个区间作为首个区间?
假设在某一种最优的选择方法中， [ l k , r k ] [l_k, r_k] [lk,rk]是首个(即最左侧的)区间，那么它的左侧没有其它区间，右侧有若干个不重叠的区间。设想一下，如果此时存在一个区间 [ l j , r j ] [l_j, r_j] [lj,rj]，使得 r j < r k r_j < r_k rj<rk，即区间 j 的右端点在区间 k 的左侧，那么我们将区间 k 替换为区间 j，其与剩余右侧被选择的区间仍然是不重叠的。而当我们将区间 k 替换为区间 j 后，就得到了另一种最优的选择方法。
我们可以不断地寻找右端点在首个区间右端点左侧的新区间，将首个区间替换成该区间。那么当我们无法替换时，首个区间就是所有可以选择的区间中右端点最小的那个区间。 因此我们将所有区间按照右端点从小到大进行排序，那么排完序之后的首个区间，就是我们选择的首个区间。
Q: 如果有多个区间的右端点都同样最小怎么办？
由于选择的是首个区间，因此在左侧不会有其它的区间，那么左端点在何处是不重要的，只要任意选择一个右端点最小的区间即可。
3.代码实现
3.1 动态规划
#写法1:超时
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
n = len(intervals)
dp = [1] * n
ans = 1
# 按照右边界排序
intervals.sort(key=lambda x: x[1])
for i in range(n):
for j in range(n - 1, -1, -1):
# 只要第 j 个区间的右端点 r_j ≤ l_i
if intervals[i][0] >= intervals[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
break
dp[i] = max(dp[i], dp[i - 1])
ans = max(ans, dp[i])
return n - ans
3.2 贪心
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
# 按照右边界排序
intervals.sort(key=lambda x: x[1])
n = len(intervals)
# 上一个选择区间的右端点right
right = intervals[0][1]
ans = 1
for i in range(1, n):
if intervals[i][0] >= right:
ans += 1
# 更新区间的右端点
right = intervals[i][1]
return n - ans
复杂度分析:
- 时间复杂度：O(nlogn)，其中 n是区间的数量。
- 空间复杂度：O(logn)，即为排序需要使用的栈空间。