美文网首页Leetcode
Leetcode 1288. Remove Covered In

Leetcode 1288. Remove Covered In

作者: SnailTyan | 来源:发表于2021-08-13 10:04 被阅读0次

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Remove Covered Intervals

2. Solution

解析:Version 1,先排序,先根据左侧排序,左侧相等再根据右侧排序,排序后相邻元素的左侧一定是非递减的。遍历相邻两个元素,有两种可能,要不左边包含右边,要不右边包含左边,如果满足条件,则移除对应元素,索引位置不变,不满足上述两种情况,则说明后一个元素的左侧及右侧都大于当前元素,索引加1,继续比较。

  • Version 1
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], x[1]))
        i = 0
        while i < len(intervals) - 1:
            if intervals[i][1] >= intervals[i+1][1]:
                intervals.pop(i+1)
            elif intervals[i][0] == intervals[i+1][0]:
                intervals.pop(i)
            else:
                i += 1
        return len(intervals)

Reference

  1. https://leetcode.com/problems/remove-covered-intervals/

相关文章

网友评论

    本文标题:Leetcode 1288. Remove Covered In

    本文链接:https://www.haomeiwen.com/subject/nqvjmltx.html