想要精通算法和SQL的成长之路 - 无重叠区间

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 无重叠区间

原题链接

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例1:

• 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
• 输出: 1
• 解释: 移除 [1,3] 后，剩下的区间没有重叠。

首先呢，既然题目给定的N个区间中，我们假设肯定有重叠的部分，那么我们怎么去判断某一部分的区间是重叠的呢？那肯定是需要比较相邻两个区间的左右边界。更重要的是，我们需要对给定的区间做一个排序。以便于比较。

那么如何做到减少最少数量的区间以达到题目要求？

核心思想：尽可能保证每个区间的范围越小越好。那么重叠的概率也就越小。

那么排序的时候这就需要分两种情况来考虑。

思路一：按照右边界来排序。那么我们应该从左往右进行遍历。那么右边界越小越好（局部最优）。右边界越小，留给下一个区间的范围可能就越大。存在交集的可能越小。那么需要删除的区间个数越少。（全局最优）

思路二：按照左边界来排序。那么我们应该从右往左进行遍历。那么左边界越大越好。左边界越大，留给上一个区间的范围可能就越大。

以右边界排序为例，如图：

我画了6个区间：分别进行了标号。也能看出来根据右边界进行排序。

1. 第二个区间和第三个区间都和黄色虚线位置存在交集，那么这两个区间应该被删除。
2. 找到第一个与黄色虚线不存在交集的区间，它的右边界作为新的交际线。也就是区间4。
3. 同理，第一个和区间4不存在交集的也就是区间6。区间5存在交集。

那么遍历的过程中计入存在交集的个数，即是最终要删除的个数。

以按照右边界排序为例，最终结果：

public int eraseOverlapIntervals(int[][] intervals) {
    // 根据右边界从小到大排序
    Arrays.sort(intervals, (o1, o2) -> o1[1] - o2[1]);
    int count = 0;
    int pre = Integer.MIN_VALUE;
    // 从左往右遍历，希望右边界越小越好
    for (int i = 0; i < intervals.length; i++) {
        // 上一个右边界（没有重复的） > 当前区间的左边界， 说明当前区间出现交集
        if (pre > intervals[i][0]) {
            // 记录交集的个数,也就是要删除的区间个数
            count++;
        } else {
            // 更新右边界
            pre = intervals[i][1];
        }
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18