合并区间

在解决许多实际问题中，合并区间是一个常见的需求。例如，在规划日程安排时，需要将相邻的时间段合并；在处理地理空间数据时，也需要整合相邻的区域。本文主要介绍如何合并给定的一组区间的技巧和算法。

1. 问题描述

假设我们有一个包含多个区间的列表（或数组），每个区间表示为一个二元组 (start, end)，任务是将所有重叠或者相邻的区间合并成尽可能少的几个区间。例如，对于输入 [[1, 3], [2, 6], [8, 10], [15, 18]]，输出应该是 [[1, 6], [8, 10], [15, 18]]。

2. 解决方案

解决这个问题的基本思路是按区间起点排序后遍历这些区间。具体步骤如下：

步骤 1: 按照起点排序

首先将所有区间按照起点进行升序排列，这样可以确保每次处理当前区间时，下一个要合并的区间必然在它的右边。

def sort_intervals(intervals):
    intervals.sort(key=lambda x: x[0])

步骤 2: 初始化结果列表和当前区间

初始化一个空的结果列表 result 和第一个区间的起点和终点来代表当前处理中的合并区间。

current_start = intervals[0][0]
current_end = intervals[0][1]

步骤 3: 遍历所有区间进行合并

遍历剩下的区间，对于每一个新的区间 (start, end)：

• 如果 start 大于当前区间的终点，则意味着没有重叠或相邻情况，需要将当前区间加入结果列表，并更新当前的起点和终点。
• 否则，说明有重叠或者相邻关系，只需要调整当前区间的终点。

for interval in intervals[1:]:
    if interval[0] > current_end:
        result.append([current_start, current_end])
        current_start = interval[0]
        current_end = interval[1]
    else:
        current_end = max(current_end, interval[1])

# 最后别忘了将最后一个区间加入结果列表
result.append([current_start, current_end])

步骤 4: 返回合并后的区间

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

def merge_intervals(intervals):
    if not intervals:
        return []
    
    sort_intervals(intervals)
    result = []
    current_start = intervals[0][0]
    current_end = intervals[0][1]
    
    for interval in intervals[1:]:
        if interval[0] > current_end:
            result.append([current_start, current_end])
            current_start = interval[0]
            current_end = interval[1]
        else:
            current_end = max(current_end, interval[1])
    
    result.append([current_start, current_end])
    return result

3. 示例代码

下面是一个完整的示例代码，展示了如何调用上述函数来合并区间。

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
merged_intervals = merge_intervals(intervals)
print(merged_intervals)  # 输出: [[1, 6], [8, 10], [15, 18]]

通过上述方法，我们可以有效地合并区间以解决实际问题中的相关需求。这种方法简洁明了，在处理大量数据时也能保持较高的效率。