https://leetcode-cn.com/problems/merge-intervals/
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
用栈来保存左边界,一旦出现右边界比左边界高,就退栈,为0就出一个输出结果
Python3 Code:
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
lList,rList = [],[]
for i in intervals:
lList.append(i[0])
rList.append(i[1])
lList.reverse()
rList.reverse()
# lList.sort(reverse=True)
# rList.sort(reverse=True)
stack = []
resList = []
while len(lList) !=0 or len(rList) != 0:
temp = None
# print(lList,rList,stack,resList)
if lList and len(stack) == 0:
pop = lList.pop()
stack.append(pop)
temp = pop
else:
if lList and rList:
if lList[-1]<= rList[-1]:
stack.append(lList.pop())
else:
lastL = stack.pop()
lastR = rList.pop()
if len(stack) == 0:
resList.append([lastL,lastR])
elif len(rList) != 0:
lastL = stack.pop()
lastR = rList.pop()
if len(stack) == 0:
resList.append([lastL, lastR])
return resList
复杂度分析
令 n 为数组长度。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。