题目
给出一个区间的集合，请合并所有重叠的区间。
例子
mergeInterval([[1,3],[8,10],[15,18],[2,6]]) -> [[1,6],[8,10],[15,18]]
mergeInterval([[4,5],[1,4]]) -> [[1,5]]假设
- 输入的二维数组不为空
tips
- 先对区间进行排序
答案
解法1
def mergeInterval(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# 如果列表为空，或者当前区间与上一区间不重合，直接添加
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# 否则的话，我们就可以与上一区间进行合并
merged[-1][1] = max(merged[-1][1], interval[1])
return merged性能：
- 时间复杂度
O(nlogn) - 空间复杂度
O(n)
关键点：
- 先对区间进行排序