Medium

题目描述

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

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

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

示例 1：

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

示例 2：

输入：intervals = [[1,4],[2,3]]
输出：1

提示：

  • 1 <= intervals.length <= 1000
  • intervals[i].length == 2
  • 0 <= li < ri <= 10^5
  • 所有给定的区间都是独一无二的。

解题思路

这道题有两种主要解法：

解法一：暴力比较法 直接对每个区间，遍历所有其他区间检查是否被覆盖。区间 [a,b) 被区间 [c,d) 覆盖当且仅当 c <= a 且 b <= d。时间复杂度 O(n²)，适合理解但效率较低。

解法二：排序优化法（推荐） 先按起点升序排序，起点相同时按终点降序排序。这样排序后，对于当前区间，只需要向前查看是否存在能覆盖它的区间。

排序的巧妙之处：

  1. 按起点排序确保前面的区间起点 <= 当前区间起点
  2. 起点相同时按终点降序排序，确保较长的区间在前面，避免短区间被长区间覆盖的情况被遗漏

遍历排序后的数组，维护一个当前最大的右端点。如果当前区间的右端点小于等于这个最大右端点，说明当前区间被之前某个区间覆盖，可以删除；否则更新最大右端点并保留当前区间。

时间复杂度 O(n log n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        // 按起点升序排序，起点相同时按终点降序排序
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0]) {
                return a[1] > b[1];
            }
            return a[0] < b[0];
        });
        
        int count = 0;
        int maxEnd = 0;
        
        for (const auto& interval : intervals) {
            // 如果当前区间的右端点大于之前的最大右端点，说明不被覆盖
            if (interval[1] > maxEnd) {
                count++;
                maxEnd = interval[1];
            }
        }
        
        return count;
    }
};

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        # 按起点升序排序，起点相同时按终点降序排序
        intervals.sort(key=lambda x: (x[0], -x[1]))
        
        count = 0
        max_end = 0
        
        for start, end in intervals:
            # 如果当前区间的右端点大于之前的最大右端点，说明不被覆盖
            if end > max_end:
                count += 1
                max_end = end
        
        return count

public class Solution {
    public int RemoveCoveredIntervals(int[][] intervals) {
        // 按起点升序排序，起点相同时按终点降序排序
        Array.Sort(intervals, (a, b) => {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        
        int count = 0;
        int maxEnd = 0;
        
        foreach (var interval in intervals) {
            // 如果当前区间的右端点大于之前的最大右端点，说明不被覆盖
            if (interval[1] > maxEnd) {
                count++;
                maxEnd = interval[1];
            }
        }
        
        return count;
    }
}

var removeCoveredIntervals = function(intervals) {
    intervals.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]);
    
    let count = 0;
    let prevEnd = 0;
    
    for (let interval of intervals) {
        if (interval[1] > prevEnd) {
            count++;
            prevEnd = interval[1];
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型排序解法
时间复杂度O(n log n)
空间复杂度O(1)