删除被覆盖区间
难度:
标签:
题目描述
代码结果
运行时间: 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`,这个条件是否足够覆盖所有可能的被覆盖情况?
▷🦆
如果存在多个区间完全相同,这种排序和覆盖判断方式是否还有效?
▷