leetcode
leetcode 1051 ~ 1100
删除被覆盖区间

删除被覆盖区间

难度:

标签:

题目描述

代码结果

运行时间: 56 ms, 内存: 15.3 MB


// Java Stream Solution
// 思路:
// 使用流来进行区间的排序和遍历。
// 与传统方法类似,先按起点升序、终点降序排序,然后过滤掉被覆盖的区间。

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        List<int[]> list = Arrays.stream(intervals)
            .sorted((a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0])
            .collect(Collectors.toList());
        int count = 0;
        int end = 0;
        for (int[] interval : list) {
            if (interval[1] > end) {
                count++;
                end = interval[1];
            }
        }
        return count;
    }
}

解释

方法:

该题解首先对区间列表进行排序,先根据区间的右端点降序排序,然后再根据左端点升序排序。这样排序后,对于任意相邻的两个区间,如果左区间被右区间覆盖,则左区间一定在右区间的前面。接着,初始化两个变量left和right分别记录当前考察的区间的左右端点。遍历排序后的区间列表,对于每个区间,如果它的左端点大于等于left且右端点小于等于right,则说明它被当前考察的区间覆盖,计数器ans增加1。如果当前区间的左端点小于等于right且右端点大于等于right,则更新right为当前区间的右端点。如果当前区间的左端点大于right,则更新left和right为当前区间的左右端点。最后,返回区间总数减去被覆盖的区间数。

时间复杂度:

O(nlogn)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么首先根据区间的右端点进行降序排序?这样的排序逻辑对解题有什么帮助?
首先对区间的右端点进行降序排序是为了确保在处理相同左端点的多个区间时,我们优先处理右端点较大的区间。这样的排序帮助我们在遍历区间时,能够有效地处理和更新被覆盖区间的情况。当右端点较大的区间先被考虑时,其它右端点较小的区间在此基础上进行比较,如果它们的左端点相同,则它们一定被覆盖。这种排序逻辑确保了在后续的处理中,我们可以准确地识别和统计被覆盖的区间。
🦆
排序后为什么还需要根据左端点升序排序,这一步是如何影响区间比较的?
在对右端点进行降序排序后,我们需要对左端点进行升序排序以确保区间的正确比较顺序。这一步主要是为了处理在右端点相同的情况下,左端点不同的区间。通过左端点升序排序,我们可以确保对于具有相同右端点的不同区间,左端点较小的区间会先被处理。这样可以有效地识别并计算出哪些区间被左端点较大的区间覆盖,从而正确地统计未被覆盖的区间数量。
🦆
在遍历区间时,判断区间是否被覆盖的条件是`interval[0] >= left && interval[1] <= right`,这个条件是否足够覆盖所有可能的被覆盖情况?
这个条件基本足够覆盖大多数的被覆盖情况,尤其是在按照题解中的排序逻辑后。这个条件意味着如果一个区间的左端点和右端点都在当前考察的区间之内,那么它被当前考察的区间完全覆盖。然而,这个条件假设了区间的左端点和右端点完全被另一个区间包括,如果有特殊情况,如边界点的处理或者区间完全相同的情况,可能需要额外的逻辑来处理。
🦆
如果存在多个区间完全相同,这种排序和覆盖判断方式是否还有效?
如果存在多个区间完全相同,这种排序和覆盖判断方式仍然有效。首先,排序会将完全相同的区间放在一起。根据题解的逻辑,当遇到完全相同的区间时,第一个区间会被设置为参考区间,而后续的相同区间则会根据`interval[0] >= left && interval[1] <= right`的条件被判断为被覆盖。因此,这种方式可以有效处理完全相同的区间,并正确计算被覆盖的区间数量。

相关问题