合并区间是处理重叠区间问题的一种常见方法。以下是使用Python合并区间的步骤和示例代码:
步骤
1. 对区间列表按照区间的起始端点进行排序。
3. 遍历排序后的区间列表,对于每个区间:
如果当前区间与上一个合并区间有重叠(即当前区间的起始端点小于等于上一个合并区间的结束端点),则合并这两个区间。
如果当前区间与上一个合并区间没有重叠,则将当前区间添加到结果列表中。
4. 返回合并后的区间列表。
示例代码
def merge_intervals(intervals):
对区间列表按照起始端点进行排序
intervals.sort(key=lambda x: x)
merged = []
for interval in intervals:
如果合并列表不为空且当前区间与上一个合并区间有重叠
if merged and interval <= merged[-1]:
合并区间
merged[-1] = max(merged[-1], interval)
else:
添加当前区间到合并列表
merged.append(interval)
return merged
示例输入
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
调用函数并打印结果
merged_intervals = merge_intervals(intervals)
print(merged_intervals) 输出:[[1, 6], [8, 10], [15, 18]]
解释
首先,我们对输入的区间列表按照区间的起始端点进行排序。
然后,我们遍历排序后的区间列表,对于每个区间,如果它与上一个合并区间有重叠,则合并这两个区间;如果没有重叠,则将当前区间添加到结果列表中。
最后,返回合并后的区间列表。
这个算法的时间复杂度是O(n log n),因为排序操作是主导的。遍历操作的时间复杂度是O(n),所以总体时间复杂度是O(n log n)。