【题目描述】
【思路解析】
1.按照intervals中每个列表中第一个元素从小到大进行排序
2.建立一个新列表re,用于保存结果
3.遍历intervals,当re中最后一个元素的尾部值小于当前interval的头部值,说明不重合,直接将该数组加入re;否则,更新re[-1][1],取max(re[-1][1],interval[1]).
【代码】
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x:x[0])
re=[]
for interval in intervals:
if not re or re[-1][1]<interval[0]:
re.append(interval)
else:
re[-1][1]=max(re[-1][1],interval[1])
return re
时间复杂度O(nlogn)主要花费在sort上,空间复杂度在O(1)-O(n)。