接外包,有相关需求的可以联系我:Telegram | Email

Remove Covered Intervals

该文章创建(更新)于04/10/2022,请注意文章的时效性!

Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.

Solution

  • submit code
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        ret = 0
        # 按照起点升序排列
        intervals.sort(key=self.takeFirst)
        # 起点相同时降序排列
        for x in range(1,len(intervals)):
            if intervals[x][1] > intervals[x - 1][1] and intervals[x][0] == intervals[x - 1][0]:
                intervals[x][1],intervals[x - 1][1] = intervals[x - 1][1], intervals[x][1]

        left = intervals[0][0]
        right = intervals[0][1]

        for i in range(1, len(intervals)):
            # 覆盖区间
            if intervals[i][0] >= left and intervals[i][1] <= right:
                ret += 1
            # 相交区间,合并
            elif intervals[i][0] <= right and right <= intervals[i][1]:
                right = intervals[i][1]
            # 不相交的情况
            elif right < intervals[i][0]:
                left = intervals[i][0]
                right = intervals[i][1]
        return len(intervals) - ret

    def takeFirst(self, elem):
        return elem[0]
  • full code
class Solution3:
    def removeCoveredIntervals(self, intervals):
        ret = 0
        # 按照起点升序排列
        intervals.sort(key=self.takeFirst)
        # 起点相同时降序排列
        for x in range(1,len(intervals)):
            if intervals[x][1] > intervals[x - 1][1] and intervals[x][0] == intervals[x - 1][0]:
                intervals[x][1],intervals[x - 1][1] = intervals[x - 1][1], intervals[x][1]

        print(intervals)

        left = intervals[0][0]
        right = intervals[0][1]

        for i in range(1,len(intervals)):
            print(i,left,right,intervals[i][0],intervals[i][1])
            # 覆盖区间
            if left <= intervals[i][0]  and intervals[i][1] <= right:
                ret += 1
                print("Y")
            # 相交区间,合并
            elif intervals[i][0] <= right and right <= intervals[i][1]:
                right = intervals[i][1]
            # 不相交的情况
            elif right < intervals[i][0]:
                left = intervals[i][0]
                right = intervals[i][1]
        print("ret:",ret)
        return len(intervals) - ret

    def takeFirst(self, elem):
        return elem[0]

S3 = Solution3()
# print(S3.removeCoveredIntervals([[1,4],[3,6],[2,8]]))
print(S3.removeCoveredIntervals([[1,2],[1,4],[3,4]]))


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/04/10/remove-covered-intervals/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码


阿里云国际版20美元
Vultr10美元
搬瓦工 | Bandwagon应该有折扣吧?
域名 | namesiloemperinter(1美元)