What is the best sorting order for Remove Covered Intervals?

Sort intervals by start ascending and end descending to expose which intervals can cover others in a single linear pass.

Can overlapping intervals affect the count?

Yes, overlapping intervals must be checked carefully; only intervals fully covered by another are removed.

Does this approach work for large arrays up to 1000 intervals?

Yes, sorting plus a single linear scan handles arrays of length up to 1000 efficiently in O(n log n) time.

How do you detect if an interval is covered?

Compare the current interval's end with the maximum end seen so far; if it is less than or equal, it is covered.

Is Remove Covered Intervals always solvable with array and sorting pattern?

Yes, sorting exposes coverage relationships and allows linear scanning, perfectly matching the array plus sorting pattern.

#1288

Medium

auto_awesome数组·排序

LeetCode 题解工作台

删除被覆盖区间

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。只有当 c 且 b 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。在完成所有删除操作后，请你返回列表中剩余区间的数目。示例：输入： intervals = [[1,4],[3,6],[2,8]] 输出： 2 解释：区间 […

数组排序

题目描述

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

只有当 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]

lightbulb

解题思路

方法一：排序

我们可以按照区间的左端点升序排序，如果左端点相同，则按照右端点降序排序。

排序后，我们可以遍历区间，如果当前区间的右端点大于之前的右端点，说明当前区间不被覆盖，答案加一。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是区间的数量。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        ans = 0
        pre = -inf
        for _, cur in intervals:
            if cur > pre:
                ans += 1
                pre = cur
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you notice how sorting by start and reverse end helps reveal coverage?
question_mark
Can you track the maximum end to avoid checking every pair?
question_mark
How does your approach scale with 1000 intervals and nested ranges?

warning

常见陷阱

外企场景

error
Not sorting by end descending, causing smaller intervals to appear before larger ones starting at the same position.
error
Comparing every interval with all others, leading to O(n^2) inefficiency.
error
Failing to handle intervals with the same start but different lengths correctly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the list of intervals that remain instead of the count.
arrow_right_alt
Handle intervals with inclusive end points instead of half-open intervals.
arrow_right_alt
Detect all intervals fully contained within multiple overlapping intervals.

help

常见问题

外企场景

继续练习

#1296 划分数组为连续数字的集合 #1300 转变数组后最接近目标值的数组和 #1268 搜索推荐系统