文章目录[隐藏]
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]]))
