LeetCode 1288. 删除被覆盖区间

约 4 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节跳动 快手 腾讯 百度 拼多多
标签
数组 排序
目录

题目描述

✅ 1288. 删除被覆盖区间

题意分析

题目给一组区间，若区间 [c, d] 满足存在另一个区间 [a, b] 使得 a <= c 且 d <= b，就把 [c, d] 删掉，最后问还剩几个。注意「覆盖」是双端都被包住，只是端点相交（例如 [1,4] 与 [3,6]）不算覆盖，这一点决定了本题不是合并区间。

输入区间没有任何有序性承诺，而覆盖关系的判定同时牵涉左右两个端点，两两比较是 $O(n^2)$；想降到线性扫描，就必须先人为制造一个顺序，让「谁可能覆盖谁」变成单向的。

题目只要求返回剩余数量，不要求返回剩下的是哪些区间，也不要求保持原始顺序，所以我们可以放心地重排输入，用一个计数器代替真正的删除动作。

边界上要留意：区间可能完全相同（[1,4] 与 [1,4] 互相覆盖，只能留一个）；可能出现退化的点区间 [2,2]；端点是非负整数，所以最大右端点的初值取 -1 就一定小于任何合法右端点；只有一个区间时答案恒为 1。

解法：排序后维护最大右端点

核心思路

覆盖条件同时比较左右端点。先把区间按「左端点升序、左端点相同时右端点降序」排列，就能让二维关系变成一维判断：

  • 当前区间的左端点不小于此前区间；
  • 相同左端点时，较长区间先出现，能先覆盖较短区间；
  • 因而当前右端点不超过历史最大右端点时，当前区间一定被覆盖。

扫描时维护 maxRight，表示已处理区间的最大右端点。若当前右端点严格大于 maxRight，它延伸到了新的位置，没有被覆盖，计入答案并更新边界；否则跳过。

必须使用严格大于：若右端点相等，后出现区间的左端点更靠右或相同，它仍被前面的区间覆盖。

解题步骤

  1. 左端点升序排序；左端点相同时，右端点降序排序。
  2. 初始化 maxRight = -1、answer = 0。
  3. 依次扫描区间。若右端点大于 maxRight，答案加一，并更新 maxRight。
  4. 否则当前区间被历史区间覆盖，不计数。

例如 [[1,4],[3,6],[2,8]] 排序为 [[1,4],[2,8],[3,6]]。前两个右端点依次刷新到 4、8，因此都保留；最后一个右端点 6 不超过 8，被 [2,8] 覆盖，答案为 2。

代码实现

import java.util.Arrays;

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) ->
                a[0] == b[0]
                        ? Integer.compare(b[1], a[1])
                        : Integer.compare(a[0], b[0]));

        int answer = 0;
        int maxRight = -1;
        for (int[] interval : intervals) {
            if (interval[1] > maxRight) {
                answer++;
                maxRight = interval[1];
            }
        }
        return answer;
    }
}

import "sort"

func removeCoveredIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][0] == intervals[j][0] {
            return intervals[i][1] > intervals[j][1]
        }
        return intervals[i][0] < intervals[j][0]
    })

    answer, maxRight := 0, -1
    for _, interval := range intervals {
        if interval[1] > maxRight {
            answer++
            maxRight = interval[1]
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n log n)$，排序占主导，扫描为 $O(n)$。
  • 空间复杂度：由排序实现决定；算法扫描部分只使用 $O(1)$ 额外空间。

关键点总结

  • 左端点排序使覆盖者只可能出现在当前区间之前。
  • 左端点相同必须让右端点更大的区间先出现，否则短区间会被错误计数。
  • 全部历史信息可压缩成一个最大右端点，无需两两比较或真的删除元素。
  • 覆盖允许端点相等，所以只有右端点严格刷新最大值时才保留。
  • 这题与合并区间不同：相交但互不包含的 [1,4]、[3,6] 都应保留。

易错点总结

  • 相同左端点按右端点升序：[1,2] 会先于 [1,5]，两者都被计数。
  • 判断写成 right >= maxRight：右端点相同的被覆盖区间也会被保留。
  • 只根据区间相交删除：相交不等于覆盖。
  • 比较器用端点直接相减：大整数可能溢出，应使用 Integer.compare。
  • 排序后仍与所有历史区间比较：maxRight 已概括所需信息，会把复杂度退化回 $O(n^2)$。

相似题目

题目 难度 考察点
56. 合并区间 中等 相交即合并并输出区间本身，而非只数剩余个数
57. 插入区间 中等 输入已有序，考的是单个新区间的三段式归并
435. 无重叠区间 中等 按右端点升序的贪心，删的是相交区间而非被覆盖
452. 用最少数量的箭引爆气球 中等 求最少公共点数，统计的是相交分组的组数
253. 会议室 II 中等 求最大重叠层数，需要堆或差分而非单个标量
986. 区间列表的交集 中等 两个有序区间表的双指针求交，不涉及排序