LeetCode如何合并区间

# LeetCode如何合并区间

## 引言

在算法面试和编程竞赛中，区间合并（Merge Intervals）是一个经典且高频出现的问题。LeetCode上的第56题"合并区间"要求我们将所有重叠的区间合并，并返回一个不重叠的区间数组。本文将深入探讨这个问题，从基础概念到多种解法，最后给出优化技巧和实际应用场景。

## 问题描述

给定一个区间集合 `intervals`，其中 `intervals[i] = [starti, endi]`。合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需覆盖输入中的所有区间。

**示例1：**

输入: intervals = [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 合并为 [1,6]

**示例2：**

输入: intervals = [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间

## 解题思路

### 关键观察
1. **区间重叠的条件**：当两个区间A和B满足`A[1] >= B[0]`时，它们可能重叠（注意需要具体比较）
2. **合并后的区间**：合并后的新区间的起始点是两个区间中较小的`start`，结束点是较大的`end`

### 基本步骤
1. 将区间按起始点排序
2. 初始化结果列表，放入第一个区间
3. 遍历后续每个区间：
   - 如果当前区间与结果列表中最后一个区间重叠，则合并
   - 否则直接加入结果列表

## 代码实现

### Python解法
```python
def merge(intervals):
    if not intervals:
        return []
    
    # 按区间起始点排序
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:  # 有重叠
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    
    return merged

Java解法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    // 按区间起始点排序
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    
    List<int[]> result = new ArrayList<>();
    int[] newInterval = intervals[0];
    result.add(newInterval);
    
    for (int[] interval : intervals) {
        if (interval[0] <= newInterval[1]) {
            newInterval[1] = Math.max(newInterval[1], interval[1]);
        } else {
            newInterval = interval;
            result.add(newInterval);
        }
    }
    
    return result.toArray(new int[result.size()][]);
}

复杂度分析

• 时间复杂度：O(n log n)，主要来自排序操作
• 空间复杂度：O(log n)（排序所需的栈空间）或 O(n)（存储结果所需空间）

边界情况处理

实际编码时需要特别注意以下边界情况： 1. 空输入：intervals = [] 2. 单个区间：intervals = [[1,3]] 3. 完全包含的区间：[[1,4],[2,3]] → [[1,4]] 4. 不相邻但值相同的区间：[[1,4],[5,6]]不应合并

算法优化

不需要显式合并的写法

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    return merged

处理大数区间

当区间值非常大时（如达到2^31），可以考虑： 1. 使用长整型存储 2. 分治策略处理超大数据集

变种问题

1. 插入区间（LeetCode 57）

给定一组不重叠的区间和一个新区间，插入并合并

解法：先插入再合并，或直接遍历处理

2. 会议室II（LeetCode 253）

计算需要的最少会议室数量

解法：使用最小堆或时间点排序

3. 区间交集（LeetCode 986）

给定两个区间列表，找出它们的交集

解法：双指针遍历

实际应用场景

1. 日程安排系统：合并用户的可工作时间段
2. 基因序列比对：合并重叠的基因片段
3. 磁盘空间管理：合并相邻的可用空间块
4. 交通调度系统：合并车辆运行时间重叠段

常见错误与调试技巧

常见错误

1. 忘记先排序区间
2. 合并时只更新end值而忘记比较max
3. 处理最后一个区间时的边界条件

调试方法

1. 打印每次合并前后的区间状态
2. 使用可视化工具绘制区间图
3. 构造小型测试用例验证

扩展思考

1. 如果区间是开区间（如(1,3)）该如何处理？
2. 如何并行化处理超大规模的区间合并？
3. 如何实时处理动态变化的区间流数据？

总结

区间合并问题通过排序+线性扫描的解法，展示了算法设计中”预处理+贪心”的经典模式。掌握这个问题不仅能帮助我们解决LeetCode上的类似题目，更能培养处理实际工程中重叠范围类问题的思维能力。建议读者在理解基础解法后，尝试解决前文提到的各种变种问题，以深化对这一模式的理解。

参考资料

1. LeetCode官方题解 2.《算法导论》分治策略相关章节
2. 编程竞赛中的经典区间处理技巧

”`

注：本文实际字数约1800字，可根据需要补充更多实现细节或应用案例以达到精确字数要求。