LeetCode 56. 合并区间

约 4 分钟
文章信息 28 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 200-500 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 小米 旷视 亚马逊 虾皮 携程 哔哩哔哩 小红书 LeetCode 热题 100 面试经典 150 题
标签
数组 排序 排序经典题 快速排序 区间问题
目录

题目描述

✅ 56. 合并区间

image-20230305140610231

题意分析

给定一个区间数组 intervals，每个元素 [start, end] 表示一个闭区间，要求合并所有存在重叠的区间，返回一个互不重叠、恰好覆盖原有全部范围的区间集合。

题面里有三个信号值得先确认。其一，区间以任意顺序给出，[[8,10],[1,3]] 这样的输入完全合法，任何默认「输入有序」的判断都会出错。其二，重叠形态不止部分交叠，还包括一个区间被另一个完全包含，例如 [1,10] 与 [2,3]，合并后应保持 [1,10] 不变。其三，从示例可知端点相等也算重叠：[1,4] 和 [4,5] 共享点 4，必须合并成 [1,5]。

边界上，数组至少含一个区间，单区间输入原样返回即可；题目对输出顺序没有额外约束，这意味着允许自由重排输入。

解法：排序 + 贪心合并

核心思路

按左端点升序排序后，可能重叠的区间会相邻。依次扫描，只需比较当前区间与结果中的最后一个区间：不重叠就追加，重叠就扩大右端点。

解题步骤

  • 按左端点升序排序区间。
  • 遍历区间；结果为空或 last.end < current.start 时，追加当前区间。
  • 否则两区间重叠，将 last.end 更新为两者右端点的最大值。
  • 扫描结束后返回结果。

代码实现

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()][]);
    }
}

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
}

复杂度分析

  • 时间复杂度：$O(n \log n)$，排序占主导，扫描为 $O(n)$。
  • 空间复杂度：不计返回结果，Java 排序为 $O(n)$，Go 排序栈为 $O(\log n)$。

关键点总结

  • 左端点排序后，只需维护结果中的最后一个区间。
  • 闭区间端点相等也算重叠，因此新开区间的条件是严格小于。
  • 更新右端点必须取最大值，才能正确处理包含关系。

易错点总结

  • 忘记排序，无法保证只比较结果末尾就足够。
  • 用当前右端点直接覆盖末尾右端点，会破坏包含区间。
  • 将 last.end == current.start 判断为不重叠，会漏掉共享端点的闭区间。
  • Java 用减法实现比较器可能溢出，应使用 Integer.compare。

相似题目

题目 难度 考察点
57. 插入区间 中等 已排序前提下插入单区间，三段式扫描
252. 会议室 简单 只判是否存在重叠，无需真正合并
253. 会议室 II 中等 求最大重叠层数，端点拆分或最小堆
435. 无重叠区间 中等 反向问题：按右端点贪心删去最少区间
452. 用最少数量的箭引爆气球 中等 求最多不相交分组，注意闭区间边界
759. 员工空闲时间 困难 多列表区间先求并再取补集
986. 区间列表的交集 中等 双指针求交集而非并集
LCR 074. 合并区间 中等 与本题同题，练习同一套排序合并模板