难度: Medium
给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。
在完成所有删除操作后，请你返回列表中剩余区间的数目。
示例：
输入：intervals = [[1,4],[3,6],[2,8]] 输出：2 解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。
提示：
1 <= intervals.length <= 10000 <= intervals[i][0] < intervals[i][1] <= 10^5i != j：intervals[i] != intervals[j]运行时间: 56 ms
内存: 15.3 MB
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1], reverse=True)
intervals.sort(key=lambda x: x[0])
print(intervals)
left = intervals[0][0]
right = intervals[0][1]
ans = 0
for i in range(1, len(intervals)):
interval = intervals[i]
if interval[0] >= left and interval[1] <= right:
ans += 1
if interval[0] <= right and interval[1] >= right:
right = interval[1]
if interval[0] > right:
left = interval[0]
right = interval[1]
return len(intervals) - ans
该题解首先对区间列表进行排序，先根据区间的右端点降序排序，然后再根据左端点升序排序。这样排序后，对于任意相邻的两个区间，如果左区间被右区间覆盖，则左区间一定在右区间的前面。接着，初始化两个变量left和right分别记录当前考察的区间的左右端点。遍历排序后的区间列表，对于每个区间，如果它的左端点大于等于left且右端点小于等于right，则说明它被当前考察的区间覆盖，计数器ans增加1。如果当前区间的左端点小于等于right且右端点大于等于right，则更新right为当前区间的右端点。如果当前区间的左端点大于right，则更新left和right为当前区间的左右端点。最后，返回区间总数减去被覆盖的区间数。
时间复杂度: O(nlogn)
空间复杂度: O(1)
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1], reverse=True) # 根据右端点降序排序
intervals.sort(key=lambda x: x[0]) # 根据左端点升序排序
left = intervals[0][0] # 初始化left为第一个区间的左端点
right = intervals[0][1] # 初始化right为第一个区间的右端点
ans = 0
for i in range(1, len(intervals)):
interval = intervals[i]
if interval[0] >= left and interval[1] <= right:
ans += 1 # 如果当前区间被覆盖，则计数器增加
if interval[0] <= right and interval[1] >= right:
right = interval[1] # 更新right为当前区间的右端点
if interval[0] > right:
left = interval[0] # 更新left为当前区间的左端点
right = interval[1] # 更新right为当前区间的右端点
return len(intervals) - ans # 返回区间总数减去被覆盖的区间数
首先对区间的右端点进行降序排序是为了确保在处理相同左端点的多个区间时，我们优先处理右端点较大的区间。这样的排序帮助我们在遍历区间时，能够有效地处理和更新被覆盖区间的情况。当右端点较大的区间先被考虑时，其它右端点较小的区间在此基础上进行比较，如果它们的左端点相同，则它们一定被覆盖。这种排序逻辑确保了在后续的处理中，我们可以准确地识别和统计被覆盖的区间。
在对右端点进行降序排序后，我们需要对左端点进行升序排序以确保区间的正确比较顺序。这一步主要是为了处理在右端点相同的情况下，左端点不同的区间。通过左端点升序排序，我们可以确保对于具有相同右端点的不同区间，左端点较小的区间会先被处理。这样可以有效地识别并计算出哪些区间被左端点较大的区间覆盖，从而正确地统计未被覆盖的区间数量。
这个条件基本足够覆盖大多数的被覆盖情况，尤其是在按照题解中的排序逻辑后。这个条件意味着如果一个区间的左端点和右端点都在当前考察的区间之内，那么它被当前考察的区间完全覆盖。然而，这个条件假设了区间的左端点和右端点完全被另一个区间包括，如果有特殊情况，如边界点的处理或者区间完全相同的情况，可能需要额外的逻辑来处理。
如果存在多个区间完全相同，这种排序和覆盖判断方式仍然有效。首先，排序会将完全相同的区间放在一起。根据题解的逻辑，当遇到完全相同的区间时，第一个区间会被设置为参考区间，而后续的相同区间则会根据`interval[0] >= left && interval[1] <= right`的条件被判断为被覆盖。因此，这种方式可以有效处理完全相同的区间，并正确计算被覆盖的区间数量。