LeetCode 1288. 删除被覆盖区间
题目描述
题意分析
区间
[a, b)被[c, d)覆盖，要求c <= a且b <= d，也就是一个区间完整包含另一个区间。只相交、相邻或由多个区间合起来覆盖，都不满足这个删除条件。返回删除后的区间数量，不需要合并剩下的区间。题目保证所有区间互不相同，且端点非负；下面的实现会对输入区间原地排序。
解法：排序后维护最大右端点
核心思路
[!blue]
覆盖需要同时满足左右两个端点的条件。先按左端点升序排列，扫描到当前区间时，之前所有区间的左端点都不大于它，左端条件已经自动满足，只需再检查右端点。
用
maxRight保存此前区间的最大右端点。若当前右端点不超过maxRight，取得这个最大值的那个真实区间就能覆盖当前区间，直接跳过；若当前右端点更大，则此前没有区间能覆盖它，答案加一并更新maxRight。左端点相同时，必须让右端点更大的长区间排在前面。这样覆盖者总在被覆盖者之前：后面的区间要么左端点更大，要么左端相同但右端更小，都不可能反过来覆盖已经计入答案的区间，因此计数无需撤销。
被覆盖的区间右端不超过现有最大值，跳过它不会丢失后续判断所需的信息。整个扫描只需要一个最大右端点，不需要保存或合并历史区间。
解题步骤
- 按左端点升序排序；左端点相等时，按右端点降序排序。
- 初始化
answer = 0、maxRight = -1。题目端点非负，因此第一个区间一定能刷新最大值。- 从前到后读取区间：右端点大于
maxRight时，保留它、答案加一，并更新最大右端点。- 右端点小于或等于
maxRight时，当前区间已被此前某个区间覆盖，跳过即可。- 返回累计保留的数量。
代码实现
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(1)$，总辅助空间取决于排序实现。
关键点总结
[!green]
- 左端排序消去一个覆盖条件，右端最大值负责判断剩下的条件。
- 相同左端先处理长区间，保证每个被覆盖区间出现时，覆盖者已经被扫描过。
maxRight来自某一个真实区间，不代表多个区间拼接出的覆盖范围。
易错点总结
[!yellow]
- 同左端若让短区间先出现，会先把它计入答案，之后遇到长区间时又无法撤销，导致多计。
- 保留条件必须是右端点严格大于
maxRight；右端相等时，当前区间同样可能被覆盖。- 不能只与原数组上一项比较。上一项可能本身就被覆盖，更早的长区间仍能覆盖当前区间。
- 这里判断的是单个区间的包含关系，不要按重叠关系合并，也不要把部分相交的区间删除。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 56. 合并区间 | 中等 | 部分重叠时本题保留两段，不像合并区间那样生成并集；只有完全包含的区间才删除。 |
| 435. 无重叠区间 | 中等 | 原题通过删除消除全部重叠，本题只删除被完整覆盖者，剩余区间仍可相交。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！