【LeeCode数组】56 合并区间
程序员文章站
2022-07-13 21:59:19
...
想要看更加舒服的排版、更加准时的推送
关注公众号“不太灵光的程序员”
每日八点有干货推送，微信随时解答你的疑问
56 合并区间 python3
中等 数组
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
from typing import List
# 26.9%
# 执行用时：64 ms
# 内存消耗：14.5 MB
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
i = 1
intervals.sort(key=lambda x: x[0])
while i < len(intervals):
if intervals[i-1][1] >= intervals[i][0]:
intervals[i-1][1] = max(intervals[i-1][1], intervals[i][1])
intervals.pop(i)
else:
i += 1
return intervals
# 83%
# 执行用时：48 ms
# 内存消耗：14.4 MB
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if intervals:
intervals.sort(key=lambda x: x[0])
i = 1
while i < len(intervals):
if intervals[i-1][1] >= intervals[i][0]:
intervals[i-1][1] = intervals[i-1][1] if intervals[i-1][1] >= intervals[i][1] else intervals[i][1]
intervals.pop(i)
else:
i += 1
return intervals
s = Solution()
ret = s.merge([[1, 3], [2, 6], [8, 10], [15, 18]])
print(ret)
ret = s.merge([[1, 4], [4, 5]])
print(ret)
ret = s.merge([[1, 4], [0, 4]])
print(ret)
ret = s.merge([[1, 4], [0, 0]])
print(ret)
ret = s.merge([[1, 4], [0, 2], [3, 5]])
print(ret)