删除被覆盖区间-数组1288-python
程序员文章站
2022-07-12 08:37:20
...
算法思想:
区间问题思路:
-
排序。常见的排序方法就是按照区间起点排序,或者先按照起点升序排序,若起点相同,则按照终点降序排序。当然,如果你非要按照终点排序,无非对称操作,本质都是一样的。
-
画图。就是说不要偷懒,勤动手,两个区间的相对位置到底有几种可能,不同的相对位置我们的代码应该怎么去处理。
-
对于区间问题,如果没啥头绪,首先排个序看看。
python
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]):
intervals = sorted(intervals, key = lambda kv:(kv[0], -kv[1]))
res = 0
length = len(intervals)
left = intervals[0][0]
right = intervals[0][1]
for inter in intervals[1:]:
if left <= inter[0] and right >= inter[1]:
res += 1
if right >= inter[0] and right <= inter[1]:
right = inter[1]
if right < inter[0]:
left = inter[0]
right = inter[1]
return length - res