わたしの部屋

1. 题目说明#

给定一组区间 intervals，返回需要移除的最少区间数量，使剩余区间互不重叠。

这里的边界规则很重要：[1, 2] 和 [2, 3] 不算重叠。

2. 贪心思路#

这题可以转化为经典的区间调度问题。

我们不直接想“删掉哪些区间”，而是反过来想：

最多能保留多少个不重叠区间？

只要能算出“最多保留几个”，答案就很自然了：

需要删除的数量 = 总区间数 - 最多保留数量

做法很简单：

1. 按区间右端点从小到大排序。
2. 依次扫描区间。
3. 先记录上一个保留区间的右端点 preEnd。如果当前区间的左端点 start >= preEnd，说明它和前一个区间不重叠，就保留它，并把 preEnd 更新为当前区间的右端点，方便判断下一个区间。
4. 否则说明重叠了，跳过它。

为什么要按右端点排序？

直觉上，结束得越早的区间，给后面的区间留下的空间越大。

更严格地说，在当前所有可选区间中，应该优先选择右端点最小的那个。

这个结论可以这样理解：

• 假设某个最优解中，第一个被选择的区间是 B
• 如果在当前还可选择的区间里，存在一个结束更早或相同的区间 A
• 那就可以把 B 换成 A

由于 A 的右端点更小，它只会给后面的区间留出更多空间，不会更差。

所以在所有最优解里，一定存在一种方案，第一步选的是右端点最小的区间。

这也是为什么按右端点排序后，扫描会特别自然：

• 排序后，第一个区间一定最早结束，先保留它
• 下一个能选的区间，就是第一个左端点 >= preEnd 的区间
• 遇到重叠就跳过，遇到不重叠就保留

所以这个贪心是成立的。

这里再把变量说清楚：

• count：当前已经保留了多少个区间
• preEnd：上一个保留区间的右端点

扫描时只需要比较当前区间的左端点和 preEnd。如果能接上，就保留当前区间，然后把 preEnd 更新成这个区间的右端点；接不上，就跳过。

这和 LeetCode 452“用最少数量的箭引爆气球”很像，区别只是边界判断不同：
435 题里 start == preEnd 不算重叠，452 题里要把这种情况看成仍然需要继续处理。

3. 例子#

比如这些区间：

1
[1, 2], [2, 3], [3, 4], [1, 3]

按右端点排序后，顺序其实是：

1
[1, 2], [1, 3], [2, 3], [3, 4]

扫描过程如下：

• 先看 [1, 2]，它是第一个区间，直接保留，preEnd = 2
• 接着看 [1, 3]，因为 1 < 2，重叠，删掉
• 再看 [2, 3]，因为 2 >= 2，保留，preEnd = 3
• 最后看 [3, 4]，因为 3 >= 3，也保留

最终保留 3 个，删除 1 个。

4. Java 实现#

1
import java.util.Arrays;
2

3
class Solution {
4
    public int eraseOverlapIntervals(int[][] intervals) {
5
        if (intervals == null || intervals.length == 0) {
6
            return 0;
7
        }
8

9
        // 按右端点升序排序
10
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
11

12
        int count = 1; // 第一个区间一定先保留
13
        int preEnd = intervals[0][1];
14

15
        for (int i = 1; i < intervals.length; i++) {
16
            // 边界相接不算重叠
17
            if (intervals[i][0] >= preEnd) {
18
                count++;
19
                preEnd = intervals[i][1];
20
            }
21
        }
22

23
        return intervals.length - count;
24
    }
25
}

这段代码的逻辑就是：

• 先把结束最早的区间保留下来
• 以后每来一个区间，就看它能不能接在 preEnd 后面
• 能接上就保留，不能接上就放弃

这样扫描一遍，就能得到最多能保留多少个区间。

1
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
2

3
int remove = 0;
4
int preEnd = intervals[0][1];
5

6
for (int i = 1; i < intervals.length; i++) {
7
    if (intervals[i][0] < preEnd) {
8
        remove++;
9
        preEnd = Math.min(preEnd, intervals[i][1]);
10
    } else {
11
        preEnd = intervals[i][1];
12
    }
13
}

5. 复杂度分析#

• 时间复杂度：O(n log n)，主要来自排序。
• 空间复杂度：O(log n) 或 O(n)，取决于排序实现。

6. 总结#

这题只要抓住一句话就够了：

按右端点排序，优先保留结束最早的区间。

这样留下的空间最多，也就最容易保留更多区间，最后删除数自然最少。

如果再记一句实现口令，就是：

preEnd 记录上一个保留区间的右端点，遇到 start < preEnd 就跳过当前区间。