python合并所有重叠的区间|极客笔记

python合并所有重叠的区间

在处理一些区间相关的问题时，经常会遇到合并重叠区间的需求。例如，给定一组区间，要求合并所有重叠的区间，得到一个合并后的区间列表。本文将使用Python来解决这个问题。

问题描述

给定一组区间，每个区间用左右边界表示，例如：[start, end]。我们的目标是合并所有重叠的区间，即将所有有交集的区间合并为一个新的区间。

举个示例，假设给定的区间集合为：

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

其中，[1, 3]和[2, 6]是重叠的区间，可以合并为[1, 6]。[8, 10]和[15, 18]没有交集，保持原样。因此，合并后的区间列表应该是：

merged_intervals = [[1, 6], [8, 10], [15, 18]]

解决方案

思路分析

要解决这个问题，我们可以按照以下步骤进行：

对给定的区间列表按照左边界进行排序；
创建一个空的结果列表，用于存储合并后的区间；
遍历排序后的区间列表，对每个区间执行以下操作：

如果结果列表为空，或者当前区间与结果列表中最后一个区间没有重叠，则将当前区间直接添加到结果列表中；
否则，如果当前区间与结果列表中的最后一个区间有重叠，则将两个区间合并，并更新结果列表中的最后一个区间。

代码实现

下面是Python中的代码实现：

def merge(intervals):
    # 对区间列表按照左边界进行排序
    intervals.sort(key=lambda x: x[0])

    # 创建一个空结果列表
    merged = []

    # 遍历区间列表
    for interval in intervals:
        # 如果结果列表为空，或者当前区间与结果列表中最后一个区间没有重叠
        if not merged or interval[0] > merged[-1][1]:
            # 直接将当前区间添加到结果列表中
            merged.append(interval)
        else:
            # 否则，将当前区间与结果列表中的最后一个区间合并
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

在代码实现中，我们首先对区间列表进行排序，以确保按照左边界的顺序处理。然后，我们创建一个空的结果列表，并遍历排序后的区间列表。

在遍历过程中，我们根据当前区间与结果列表中的最后一个区间是否有重叠，进行不同的操作。如果结果列表为空，或者当前区间与结果列表中最后一个区间没有重叠，则将当前区间直接添加到结果列表中。否则，将当前区间与结果列表中的最后一个区间合并，即将结果列表中最后一个区间的右边界更新为当前区间的右边界与原右边界的较大值。

最后，返回合并后的结果列表。

示例运行

下面是一个示例运行的示例：

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
merged_intervals = merge(intervals)
print(merged_intervals)

输出为：

[[1, 6], [8, 10], [15, 18]]

复杂度分析

对于给定的区间集合，假设有n个区间。

时间复杂度：排序的时间复杂度为O(nlogn)，遍历区间列表的时间复杂度为O(n)，因此整体的时间复杂度为O(nlogn)。
空间复杂度：除了结果列表外，使用的额外空间为常数级别，因此空间复杂度为O(1)。

总结

本文介绍了如何使用Python来合并所有重叠的区间。通过对区间列表进行排序，然后遍历并合并重叠的区间，可以得到一个合并后的区间列表。

这种合并重叠区间的问题在实际应用中较为常见，例如合并日程安排、合并交叉时间段等。掌握了这个问题的解决方法，可以提高对区间处理的能力。

python合并所有重叠的区间