leetcode-435-Non-overlapping-Intervals

TODO

描述


Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

1
2
3
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

1
2
3
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

1
2
3
Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

分析


动态规划的思想:dp[i] 定义为以 intervals[i] 结尾的最长 non-overlapping intervals 的长,推导公式为:dp[i] = max(dp[1]+1,dp[2]+1,dp[3]+1,...,dp[i-1]+1),也可以用贪心的思想,把动态规划的推导公式写出来了,基本就能证明贪心算法的正确性了。动态规划的时间复杂度为 O(N^2), 空间复杂度为 O(N)

解决方案1(Python)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[0])
intervalsLen = len(intervals)
if intervalsLen == 0:
return 0

dp = [1 for _ in range(intervalsLen)]
for i in range(intervalsLen):
for j in range(i-1, -1, -1):
if intervals[j][1] <= intervals[i][0]:
dp[i] = max(dp[j]+1, dp[i])
break
return intervalsLen - max(dp)

相关问题


题目来源