Remove Covered Intervals

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]]))
``````

要不赞赏一下?

 微信 支付宝 PayPal Bitcoin

``https://www.emperinter.info/2022/04/10/remove-covered-intervals/``

 阿里云国际版 20美元 Vultr 10美元 搬瓦工 | Bandwagon 应该有折扣吧？ Just My Socks JMS9272283 【注意手动复制去跳转】 域名 | namesilo `emperinter`(1美元) 币安 币安