LeetCode算法刷题：如何优雅地删除被覆盖区间？

最近在刷算法题的时候，遇到了一道非常经典的区间处理问题——LeetCode 1288. 删除被覆盖区间。

区间覆盖关系的直观图示，展示了长区间如何覆盖短区间。

这道题的题目描述很简单：给你一个区间列表，请你删除其中被其他区间完全覆盖的区间，返回剩下的区间数量。虽然看起来不难，但里面的细节处理非常有讲究，尤其是排序策略的选择，直接决定了代码的复杂度。

今天我们就来拆解一下这道题，看看如何从“暴力思考”进化到“最优解”。

题目核心痛点

所谓的“被覆盖区间”，比如区间 [1, 4] 就可以覆盖 [2, 3] 或者 [1, 2]。如果给定数组 [[1,4],[2,3],[3,4]]，[2,3] 被覆盖了，[3,4] 没有被覆盖，[1,4] 是老大，所以最后结果是 2。

直观的想法是两两比较，但这复杂度瞬间就爆表了。既然是区间问题，排序 永远是我们的第一反应。排好序之后，我们通常只需要一次遍历就能解决问题。

左端点升序、右端点降序的排序策略对比图。

思路一：常规排序的陷阱

一开始，我（以及很多朋友）最容易想到的排序方式是：

1. 左端点升序排列（让区间从左到右排好队）。
2. 右端点也升序排列（保持自然顺序）。

按照这个逻辑，如果后面的区间起始点比前一个大，但结束点却比前一个小，那肯定是覆盖。但是！如果起始点相同呢？

比如 [1, 4] 和 [1, 2]。按照上面的排序规则（右端点升序），[1, 2] 会排在前面。这就尴尬了，后面那个长的区间 [1, 4] 反而会“吃掉”前面的 [1, 2]。这就导致了我们在遍历的时候，不仅要判断“当前是否被前一个覆盖”，还得反过来判断“前一个是否被当前覆盖”。

代码逻辑瞬间变得支离破碎，需要维护两个变量 prevStart 和 prevEnd，还要写一堆 if-else 来处理这种反向覆盖的情况。这显然不够优雅。

思路二：最优解——降序排列的妙用

怎么才能避免这种“反向覆盖”的判断呢？

关键点在于左端点相同时的处理。

如果我们改变排序策略：

1. 左端点升序（不变）。
2. 右端点降序（注意这里是降序！）。

这样会发生什么？同样面对 [1, 4] 和 [1, 2]，因为左端点相同，而 4 > 2，所以 [1, 4] 会排到前面。

这时候，我们只需要维护一个变量 right（表示当前遇到的最远右边界）。

• 遍历到第一个区间 [1,4]，更新 right = 4。
• 遍历到第二个区间 [1,2]，发现它的右端点 2 <= right，直接判定为被覆盖，删除！
• 遍历到第三个区间（假如是 [2, 3]），左端点变大，右端点 3 <= right (4)，被覆盖。
• 遍历到更后面的区间（假如是 [5, 6]），左端点变大，右端点 6 > right，更新 right = 6，保留。

妙在哪里？

通过将左端点相同的区间按“从大到小”排列，我们保证了在同一时间点，遇到的第一个区间肯定是最长的。接下来的同起点小区间只会被它覆盖，根本不可能反过来覆盖它。这直接帮我们省去了“反向判断”的复杂逻辑！

代码实现

经过上面的分析，代码就非常清爽了。这里用 Java 实现一下（C++ 思路完全一致）。

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        // 自定义排序：左升序，右降序
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1]; // 关键：左端点相同时，右端点降序
            } else {
                return a[0] - b[0]; // 左端点升序
            }
        });

int right = 0;
        int ans = intervals.length; // 初始假设都需要保留

for (int[] interval : intervals) {
            // 如果当前区间的右边界不超过之前记录的最大right，说明被覆盖了
            if (interval[1] <= right) {
                ans--; // 计数减一
            } else {
                // 没被覆盖，更新最大右边界
                right = interval[1];
            }
        }
        return ans;
    }
}

总结

做区间类题目时，排序的 Comparator 写法往往决定了后续遍历逻辑的复杂度。

• 如果是求“合并区间”或者“区间交集”，通常双端都升序即可。
• 但如果涉及到覆盖关系（如本题），一定要小心左端点相同的情况。将左端点相同的区间按右端点降序排列，是一个极其有效的贪心策略，能让代码量直接缩减 30% 以上，逻辑也更不容易出错。

希望大家以后遇到类似区间问题时，能灵活运用这个“升序+降序”的小技巧！