做羽毛球网站,wordpress 分享 微信,建设培训网站,南阳定制网站制作价格低要实现合并区间#xff0c;你可以按照区间的起始位置对区间进行排序#xff0c;然后依次遍历区间#xff0c;将重叠的区间合并。以下是实现的示例代码#xff1a;
def merge_intervals(intervals):if not intervals:return []# 按照区间的起始位置进行排序intervals.sort(…要实现合并区间你可以按照区间的起始位置对区间进行排序然后依次遍历区间将重叠的区间合并。以下是实现的示例代码
def merge_intervals(intervals):if not intervals:return []# 按照区间的起始位置进行排序intervals.sort(keylambda x: x[0])merged [intervals[0]] # 初始化合并后的区间列表将第一个区间加入其中for interval in intervals[1:]:if interval[0] merged[-1][1]: # 如果当前区间与合并后的最后一个区间有重叠merged[-1] [merged[-1][0], max(merged[-1][1], interval[1])] # 更新合并后的最后一个区间else:merged.append(interval) # 否则将当前区间加入合并后的列表return merged# 示例区间列表
intervals [[1, 3], [2, 6], [8, 10], [15, 18]]# 合并区间
merged_intervals merge_intervals(intervals)
print(Merged intervals:, merged_intervals)在上面的代码中我们首先对区间列表按照区间的起始位置进行排序。然后遍历排序后的区间列表依次将区间与合并后的最后一个区间进行比较如果有重叠则更新合并后的最后一个区间的结束位置如果没有重叠则将当前区间加入合并后的列表中。
这个算法的时间复杂度为O(nlogn)其中n是区间的个数因为排序的时间复杂度为O(nlogn)遍历一次区间列表的时间复杂度为O(n)。
