LeetCode 1288. 删除被覆盖区间

链接一、题目给你一个区间列表请你删除列表中被其他区间所覆盖的区间。只有当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^5对于所有的i ! jintervals[i] ! intervals[j]四、解题class Solution: def removeCoveredIntervals(self, intervals: List[List[int]]) - int: intervals.sort(keylambda x: (x[0], -x[1])) # Python原地排序方法直接修改原列表不返回新列表 ans 0 #用于记录未被覆盖的区间个数(即最终答案)。初始为0 max_end -1 #用于记录目前遍历过的所有区间中右端点的最大值。初始化为-1 for left, right in intervals: # 按排序后的顺序依次取出每个区间的左右端点 if right max_end: # 未被覆盖 # 当满足条件时说明当前区间是一个未被覆盖的区间于是 ans 1 #计数增加。 max_end right #更新最大右端点因为当前区间的右端点比之前所有的都大这是由条件保证的它成为新的最右边界。 return ans # 遍历结束后ans就是所有未被覆盖的区间个数即删除被覆盖区间后剩余的数量。五、解题思路解题思路详解核心思想是排序贪心扫描通过巧妙的排序将原本需要两两比较的覆盖关系转化为一次从左到右的线性判断从而高效求出答案。5.1.问题本质回顾-给定区间[l,r]若存在另一个区间[L,R]满足L≤l且r≤R则[l,r]被覆盖应当删除。-目标返回剩余未被覆盖的区间个数。5.2.核心思路排序以简化比较直接暴力两层循环检查每个区间是否被其他区间覆盖时间复杂度为O(n²)且需要处理相等边界的细节。5.3.排序策略左升、右降pythonintervals.sort(keylambda x: (x[0], -x[1]))-第一关键字左端点升序→ 保证扫描时左边的区间起点不晚于右边的区间这是“覆盖”的必要条件。-第二关键字右端点降序即-x[1]升序→当左端点相同时右端点大的区间排在前面。这样做的目的是在起点相同的一组区间中先处理覆盖能力最强的那个右端点最大确保它能正确覆盖掉后续起点相同但终点较小的区间避免误计数。5.4.扫描过程维护max_end遍历排序后的区间用变量max_end记录到目前为止所有已扫描区间的右端点最大值。-若当前区间rightmax_end-说明之前的任意一个区间即使左端点≤当前左端点其右端点也小于当前右端点因此不可能覆盖当前区间因为覆盖需要右端点 ≥ 当前右端点。- 所以当前区间未被覆盖答案ans加1并更新max_end right因为它的右端点比之前所有都大。-若right≤max_end-说明存在某个之前的区间其左端点≤当前左端点排序保证且右端点 ≥ 当前右端点因为max_end是最大值必≥当前右端点。-因此当前区间被覆盖跳过不计数。5.5.复杂度分析-时间复杂度排序O(nlog n)扫描O(n)总体O(nlog n)。-空间复杂度原地排序只用了常数个额外变量O(1)。六、sort排序sort()函数排序