合并区间
Merge Intervals
本机进度仅保存在当前浏览器
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例：intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]，输出 [[1, 6], [8, 10], [15, 18]]。
解题思路
- 先按左端点排序，使所有可能重叠的区间相邻，扫描一遍即可完成合并。
- 维护当前合并区间：下一个区间左端点 <= 当前右端点则重叠，右端点取两者较大值（覆盖包含关系）。
- 不重叠则把当前区间存档，开启新区间。
参考实现
查看参考实现Python · 建议先自行作答
def merge(intervals):
intervals.sort(key=lambda x: x[0])
res = []
for start, end in intervals:
# 与上一区间重叠则延伸右端点
if res and start <= res[-1][1]:
res[-1][1] = max(res[-1][1], end)
else:
res.append([start, end])
return res