LeetCode 56. 合并区间

约 4 分钟
文章信息 29 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 200-500 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 亚马逊 美团 拼多多 京东 小米 百度 网易 小红书 快手 滴滴 携程 B站 虾皮 金山 旷视 猿辅导
标签
数组 排序

题目描述

✅ 56. 合并区间

image-20260928184510074

题意分析

输入若干个闭区间，需要把互相重叠的部分合并，返回一组互不重叠的区间。合并前后覆盖的所有位置必须相同，不能遗漏原区间，也不能把中间未被覆盖的空隙补进去。

闭区间包含两端，因此一个区间的右端点等于另一个区间的左端点时，也需要合并。区间还可能重复、相互包含或通过其他区间连接成一整段，输入顺序不保证有序。

解法：排序 + 贪心合并

核心思路

[!blue]

如果按原顺序处理，当前区间可能与结果中的任意一段重叠，难以只比较一次就确定位置。先按左端点升序排序，就能保证后来的区间不会从更靠左的位置开始。

扫描时维护结果 merged，其中的区间始终按位置排列且互不重叠。只需检查最后一段 last：更早各段的右端点都小于 last 的左端点，而当前区间的左端点不小于 last 的左端点，因此不可能再与更早各段相交。

若 last.end < current.start，两段之间有空隙。后续区间的起点只会更大，也无法填补这个空隙，所以 last 已经确定，可以把当前区间作为新的一段追加。

否则两段重叠或共享端点，应合成一段。左端点仍取 last.start，右端点取两者的最大值。取最大值既能扩大覆盖范围，也能让被包含的区间不缩短原来的范围。每次合并后继续与新的最后一段比较，连锁重叠便会自然合成一个区间。

解题步骤

  1. 按左端点升序排列所有区间，创建空结果列表 merged。
  2. 依次取出当前区间。若结果为空，直接放入结果。
  3. 若最后一段的右端点严格小于当前左端点，说明存在间隔，追加当前区间。
  4. 否则将最后一段的右端点更新为两个右端点的较大值，不新增区间。
  5. 返回结果。代码会原地排序，并复用输入中的区间数组或切片，因此合并时也可能修改输入区间的右端点。

代码实现

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (first, second) -> Integer.compare(first[0], second[0]));
        List<int[]> merged = new ArrayList<>();

        for (int[] interval : intervals) {
            // 闭区间端点相等仍重叠，严格分离时才新开一段。
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
                continue;
            }

            int[] last = merged.get(merged.size() - 1);

            // 只扩大最后一段的右端；这里修改的是复用的原区间数组。
            last[1] = Math.max(last[1], interval[1]);
        }

        return merged.toArray(new int[merged.size()][]);
    }
}

import "sort"

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i int, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    merged := make([][]int, 0, len(intervals))
    for _, interval := range intervals {
        // 闭区间端点相等仍重叠，严格分离时才新开一段。
        if len(merged) == 0 || merged[len(merged)-1][1] < interval[0] {
            merged = append(merged, interval)
            continue
        }

        last := merged[len(merged)-1]
        // 只扩大最后一段的右端；这里修改的是复用的原区间切片。
        if interval[1] > last[1] {
            last[1] = interval[1]
        }
    }

    return merged
}

复杂度分析

设输入有 n 个区间。

  • 时间复杂度：$O(n \log n)$，排序需要 $O(n \log n)$，合并扫描只需 $O(n)$。
  • 空间复杂度：$O(n)$，结果最多保存 n 段。不计结果存储时，Java 对对象数组排序还需要 $O(n)$ 辅助空间，Go 排序使用 $O(\log n)$ 调用栈。

关键点总结

[!green]

  • 按左端点排序后，只需要检查最后一段；更早各段已经与当前及后续区间隔开。
  • 出现严格空隙才新建一段，共享端点仍属于同一段。
  • 合并是在保持左端点的同时扩大右端点，遇到包含关系时范围保持不变。

易错点总结

[!yellow]

  • 忘记排序就只比较结果末尾，可能漏掉与更早结果的重叠。
  • 直接用当前右端点覆盖末尾右端点，会在当前区间被包含时错误地缩小范围。
  • 把端点相等判断为不重叠，会漏掉闭区间共享的端点。
  • 排序只需要比较起点；起点相同时，无论哪个区间先出现，右端点取最大值都能正确合并。

相似题目

题目 难度 关联与区别
57. 插入区间 中等 同样维护互相重叠的区间，原题输入已有序且不重叠，只需插入一个新区间后合并。
435. 无重叠区间 中等 同样按区间关系处理重叠，原题删除最少区间保持不相交，本题把重叠部分合成并集。
986. 区间列表的交集 中等 按起点排序后合并重叠区间；本题输出区间并集，该题以双指针枚举两个区间表的交集。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/35203621
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！