LeetCode 1288. 删除被覆盖区间

Categories:

题目描述
思路分析
1. 解法一：排序后线性扫描（推荐）
相似题目

题目描述

✅ 1288. 删除被覆盖区间

思路分析

解法一：排序后线性扫描（推荐）

核心思路：

先按起点升序、终点降序排序。

维护当前最大右端点 maxEnd。

若当前区间的右端点 <= maxEnd，说明被覆盖；否则更新计数与 maxEnd。

复杂度分析：

时间复杂度：O(n log n)，排序开销。

空间复杂度：O(1) 或 O(log n)（排序栈开销）。

import java.util.Arrays;

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });

        int count = 0;
        int maxEnd = -1;
        for (int[] it : intervals) {
            if (it[1] <= maxEnd) {
                continue;
            }
            count++;
            maxEnd = it[1];
        }
        return count;
    }
}

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]
	})

	count := 0
	maxEnd := -1
	for _, it := range intervals {
		if it[1] <= maxEnd {
			continue
		}
		count++
		maxEnd = it[1]
	}
	return count
}

相似题目

题目	难度	考察点
1288. 删除被覆盖区间	中等	排序、扫描
56. 合并区间	中等	排序、区间
57. 插入区间	中等	排序、区间
435. 无重叠区间	中等	贪心、区间
452. 用最少数量的箭引爆气球	中等	贪心、区间
986. 区间列表的交集	中等	双指针、区间

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/75597823