1288.删除被覆盖区间：排序(非二重循环暴力)

【LetMeFly】1288.删除被覆盖区间：排序(非二重循环暴力)

力扣题目链接：https://leetcode.cn/problems/remove-covered-intervals/

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

 

示例：

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

 

提示：​​​​​​

• 1 <= intervals.length <= 1000
• 0 <= intervals[i][0] < intervals[i][1] <= 10^5
• 对于所有的 i != j：intervals[i] != intervals[j]

解题方法一：二重循环暴力

由于数据量最大只有$1000$，所以可以二重循环一一对比，查看某个区间是否被包含在其他区间中。

• 时间复杂度$O(n^2)$，其中$n=len(intervals)$
• 空间复杂度$O(1)$

解题方法二：排序（贪心）

按照其实时间从小到大排序，那么按顺序遍历的过程中，后遍历的区间起始时间一定比先遍历区间的晚。那么如果前面有区间的截止时间在此区间之后，是不是说明这个区间一定被覆盖掉了。

所以排序依据：若起始时间不同则起始时间小的优先，否则截止时间大的优先。

• 时间复杂度$O(n\log n)$
• 空间复杂度$O(\log n)$

AC代码

C++

/*
 * @LastEditTime: 2026-07-07 22:16:53
 */
class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
        });
        int ans = intervals.size();
        for (int i = 0, n = intervals.size(), r = 0; i < n; i++) {
            ans -= intervals[i][1] <= r;
            r = max(r, intervals[i][1]);
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2026-07-07 22:19:44
'''
from typing import List

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        ans = len(intervals)
        R = 0
        for l, r in intervals:
            ans -= r <= R
            R = max(R, r)
        return ans

Java

/*
 * @LastEditTime: 2026-07-07 22:31:39
 */
import java.util.Arrays;

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
        });
        int ans = intervals.length;
        int r = 0;
        for (int[] v : intervals) {
            if (v[1] <= r) {
                ans--;
            } else {
                r = v[1];
            }
        }
        return ans;
    }
}

Go

/*
 * @LastEditTime: 2026-07-07 22:28:57
 */
package main

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]
    })
    
    ans := len(intervals)
    r := 0
    for _, v := range intervals {
        if v[1] <= r {
            ans -= 1
        }
        r = max(r, v[1])
    }
    return ans
}

Rust

/*
 * @LastEditTime: 2026-07-07 22:36:22
 */
impl Solution {
    pub fn remove_covered_intervals(mut intervals: Vec<Vec<i32>>) -> i32 {
        intervals.sort_by_key(|x| (x[0], -x[1]));
        let mut ans = intervals.len() as i32;
        let mut r = 0;
        for v in intervals.iter() {
            if v[1] <= r {
                ans -= 1;
            } else {
                r = v[1];
            }
        }
        return ans;
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源