LeetCode 435. 无重叠区间_无重叠区间 超时

LeetCode 435. 无重叠区间

题目描述

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
1
2
3
4
5

无重叠区间
提示：

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

一、解题关键词

最小数量 、不重叠 
1

二、解题报告

1.思路分析

最值问题 联想到动态规划 贪心 and 排序

2.时间复杂度

3.代码示例

class Solution {
    public int eraseOverlapIntervals(int[][] nums) {
  int length = nums.length;
        if (length == 0){
            return 0;
        }
        Arrays.sort(nums, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int right = nums[0][1];
        int ans = 1;
        for (int i = 1; i < length; i++) {
            if (nums[i][0] >= right){
                ++ans;
                right = nums[i][1];
            }
        }
        return length - ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.知识点

1、可以使用动态规划，但是会超时，这个题动态规划解法可以联系最长递增子序列的知识点

1
2

---

总结

知识都是互通的。学会融合