欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

删除被覆盖区间-数组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