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 | Input: intervals = [[1,2],[2,3],[3,4],[1,3]] |
Example 2:
1 | Input: intervals = [[1,2],[1,2],[1,2]] |
Example 3:
1 | Input: intervals = [[1,2],[2,3]] |
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 | class Solution: |