[数据结构与算法]Java描述 LeetCode，435. Non-overlapping Intervals 不重复的间隔

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

1-1：题目

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:

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:

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:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/non-overlapping-intervals

1-2：解法1 动态规划

1-2-1：idea

??题目的意思是删除区间使剩下的区间不存在重复的范围，要求删除的最少。问题等价为：在这些区间中找到最多的区间，这些区间没有重复的范围。

??首先先按照左区间进行排序，之后就可以用dp来做了。

• 定义状态dp[i]：intervals[0:i] 其中intervals[i]必选，最多有dp[i]个区间不存在重复范围。
• 状态转移方程：很明显我们知道这里的区间（区间可以看成是一个整体）不一定是连续的，所以如果你做过这道题Java描述 LeetCode，300. Longest Increasing Subsequence，并且输出最小的，你就会懂了。只要这边intervals[i] >= intervals[j]，（注意相等不算重合的，从example2可以看出），就可以intervals[i] = max(intervals[j]) +1;

1-2-2：代码

public static int removeMinIntervals(int[][] intervals) {
    int n = intervals.length;
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

    int[] dp = new int[n];

    Arrays.fill(dp, 1);
    int max = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (intervals[i][0] >= intervals[j][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
                max = Math.max(max, dp[i]);
            }
        }
    }
    System.out.println(Arrays.toString(dp));
    return n - max;
}
时间复杂度O(n^2)，空间复杂度O(n)

当然这个时间复杂度是O(n^2)并不能AC，但是算是一种思路。

1-3：解法2贪心算法

1-3-1：idea

??Java描述 LeetCode，452. Minimum Number of Arrows to Burst Balloons 用最少的箭打破气球，我们把本道题和452道题目比较起来，就可以发现这两个很像，好像都是要有重叠的思维在里面。同样我们先把本题转换成：求最大不重复区间的个数。那么贪心的思路在哪？冥冥之中，自然要排序了。这次按照右区间先排序，为啥呢？我们只有让小的右区间先加入进来，才能保证更大的范围给后面的区间，试想下，右区间的大小其实就限制了左区间的大小了，它在数轴上最长不超过右区间的大小，这样后面就有大范围留下，给剩余的区间。

1-3-2：代码

public static int removeMinIntervals2(int[][] intervals) {
    int n = intervals.length;
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));
    System.out.println(Arrays.deepToString(intervals));
    int ans = 1;
    int pos = intervals[0][1];
    for (int i = 1; i < n; i++) {
        if (intervals[i][0] >= pos) {
            pos = intervals[i][1];
            ans++;
        }
    }

    return n - ans;
}

时间复杂度O(nlogn) 空间复杂度O(logn)

??代码和T452差不多，但是注意：因为比较的时候，intervals[i]左区间>=pos右区间时候ans++，这里的ans 代表的是不重复的区间的数目，所以剩余的就是要被删掉的了。

1-4：总结

??今天的第二道贪心题目我是没有想到根据右区间排序然后做的，好像跟上道题稍微变换了下，就不会了，zzz。继续加油！主要是思路上没有想到。