力扣百题通

56. 合并区间 (Medium)

Properties2
description以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i]。
tags数组, 排序

10分钟阅读

56. 合并区间 (Medium)

专题归类： 数组 · 排序 LeetCode 链接： https://leetcode.cn/problems/merge-intervals/

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 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 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4

题目详细分析

数据范围分析：

  • 区间数量最多 10^4，O(n^2) 的直接比较会超时，但 O(n log n) 的排序 + O(n) 扫描可行。
  • 起点和终点都在 0~10^4 之间，比较小，但题目不要求利用这个特性。

输入输出特征：

  • 输入是二维数组，每个元素是一个长度为 2 的数组 [start, end]。
  • 输出也是二维数组，但合并了重叠区间后数量可能减少。
  • 区间按 start 和 end 的定义：start <= end，所以不会出现 [5,3] 这种非法区间。

边界条件：

  • 只有一个区间 → 直接返回原数组。
  • 区间完全包含另一个区间 → 如 [1,5] 和 [2,3] 合并为 [1,5]。
  • 区间端点相接（如 [1,4] 和 [4,5]）→ 视为重叠，需要合并。
  • start 和 end 可以相等（区间长度为 0 的点）。
  • 所有区间都不重叠 → 返回原数组（但排序后）。

隐藏条件：

  • 输入可能不是按起点排序的，必须先排序。
  • 合并操作只看相邻区间（排序后），不需要两两比较所有区间。
  • 相接 = 重叠（即 interval[0] <= merged[-1][1] 时需要合并，包含等于情况）。

小白版直白理解

想象你有几段绳子，每段绳子有起点和终点。有的绳子叠在一起，有的分开。

你的任务：把叠在一起的绳子接成一根长绳，最后只保留不重叠的几根绳子。

比如你手上有：

  • 绳子 A：1 米到 3 米处
  • 绳子 B：2 米到 6 米处

A 和 B 有重叠部分（2-3 米），所以把它们接成一根新绳子：1 米到 6 米。

做法就和我们整理数据线一样：

  1. 先把所有绳子按起点排好序（这样就知道哪根在前）
  2. 从第一根开始，如果下一根的起点在当前绳子的范围内，就把它接上（延长当前绳子的终点到更远的位置）
  3. 如果下一根的起点已经超出了当前绳子的终点，说明它们不重叠，保存当前绳子，开始处理下一根

解题思路

思路一：排序 + 一次扫描（推荐）

核心洞察：

按起点排序后，重叠的区间必然在排序后相邻。这样只需要一次遍历，在遍历过程中维护一个”当前合并区间”：

  • 如果新区间的起点 <= 当前合并区间的终点 → 重叠，合并（更新终点为两者终点的较大值）
  • 否则 → 不重叠，将当前合并区间加入结果，开始新的合并区间

代码实现技巧： 利用 merged[-1] 表示结果数组中最后一个（即当前正在合并的）区间，可以让代码非常简洁。

def merge(intervals):
    if not intervals:
        return []
    
    # 按区间起点升序排序（这是关键前提）
    intervals.sort(key=lambda x: x[0])
    merged = []
    
    for interval in intervals:
        # 如果 merged 为空，或者当前区间与 merged[-1] 不重叠
        if not merged or interval[0] > merged[-1][1]:
            merged.append(interval)
        else:
            # 重叠：合并区间——更新终点为较大值
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    return merged

复杂度： O(n log n) 时间（排序），O(n) 空间（结果数组）。排序是算法的主要瓶颈。

思路二：排序 + 双指针扫描（另一种写法）

维护两个指针 start 和 end 表示当前合并区间，遍历时发现重叠就更新 end，不重叠就把 [start, end] 加入结果。

def merge_two_pointer(intervals):
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: x[0])
    result = []
    start, end = intervals[0][0], intervals[0][1]
    
    for i in range(1, len(intervals)):
        if intervals[i][0] <= end:
            # 重叠，更新 end
            end = max(end, intervals[i][1])
        else:
            # 不重叠，保存当前区间，开始新区间
            result.append([start, end])
            start, end = intervals[i][0], intervals[i][1]
    
    # 添加最后一个区间
    result.append([start, end])
    return result

思路三：差分数组法（进阶，适合批量区间操作）

将每个区间看作「在起点+1，在终点+1后-1」的事件，然后扫描所有事件点。这个方法在处理大量区间重叠统计时更高效，但对本题来说不如排序+扫描直接。

def merge_diff(intervals):
    # 差分数组思想：将区间端点映射为事件
    events = []
    for start, end in intervals:
        events.append((start, 0))    # 0 表示起点
        events.append((end, 1))      # 1 表示终点
    
    events.sort()  # 按位置排序
    
    result = []
    count = 0
    start = None
    
    for pos, typ in events:
        if typ == 0:  # 遇到起点
            if count == 0:
                start = pos  # 开始一个新的合并区间
            count += 1
        else:  # 遇到终点
            count -= 1
            if count == 0:
                result.append([start, pos])
    
    return result

注意： 差分法在本问题中不如排序+扫描直观，但适用于需要批量查询「某个点被多少个区间覆盖」的场景。

易错点

  • 忘记排序：未排序直接扫描会导致合并错误，因为重叠的区间可能没有相邻。
  • 等于号处理：interval[0] <= end 包含等于情况，因为 [1,4] 和 [4,5] 端点相接也算重叠。
  • 更新终点：合并时要取 max(end, interval[1]) 而不是直接用 interval[1]——因为新区间可能完全包含在当前合并区间内。
  • 最后一个区间：遍历结束后别忘了把最后一个合并区间加入结果。
  • 空输入：如果 intervals 为空，直接返回空列表。
  • 排序稳定性：按起点排序即可，起点相同时顺序不影响结果。

框架提炼

区间合并通用模板：

def merge_intervals(intervals):
    # Step 1: 排序（按起点）
    intervals.sort(key=lambda x: x[0])
    
    # Step 2: 初始化结果列表
    merged = []
    
    # Step 3: 遍历所有区间
    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

区间问题通用思考框架：

  1. 排序（按起点或终点）——让区间有序
  2. 遍历 + 维护当前状态（当前合并区间）
  3. 判断相邻区间的关系：重叠/不重叠/包含/相交
  4. 根据关系更新状态或输出结果

可扩展到的区间问题：

关联题目

  • 57-插入区间 — 在已排序且不重叠的区间列表中插入一个新区间，需要合并重叠部分。可以用本题的合并逻辑作为子函数。
  • 435-无重叠区间 — 目标相反：移除最少的区间使剩余区间不重叠。贪心策略是按终点排序。
  • 452-用最少数量的箭引爆气球 — 同样处理区间重叠，但要求的是最少箭数（即重叠区间分组数）。按终点排序后贪心射箭。
  • 763-划分字母区间 — 合并区间的变体，将每个字母的首次和末次出现位置视为区间，合并后得到划分。

关系图谱

反向链接