LeetCode LCR 074. 合并区间

约 5 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 排序 LCR

题目描述

✅ LCR 074. 合并区间

image-20260929005731400

题意分析

将所有相交的闭区间合并，返回互不重叠且恰好覆盖原输入的区间集合。共享端点也算相交，完全包含与长度为零的区间都需要按同样规则处理。

输入没有顺序。先按左端点排序，就能从左到右维护一段尚未结束的合并结果，避免反复寻找任意两段是否可以合并。题目保证至少有一个区间，可以用排序后的第一段初始化状态。

解法：排序后线性合并

核心思路

[!blue]

按左端点升序排列后，用 [st,ed] 表示目前仍可能与后续输入相交的合并段。它覆盖当前这一组已处理区间的并集；已经放入答案的更早合并段则已经确定，不需要再修改。

读取新区间 [s,e] 时，若 s <= ed，它与当前合并段相交。排序保证 s >= st，左端无需变化，右端扩展为 max(ed,e)。取最大值是为了保留已有覆盖范围，不能被一个完全包含在当前段中的短区间缩回去。

若 s > ed，新区间已经与当前段分离。后面所有区间的左端都不小于 s，也就不可能再延伸这段，因此可以把 [st,ed] 写入答案，并用新区间开始下一段。

判断对象始终是累计合并后的区间，而不是仅比较两个相邻的原始区间。前面的长区间可能跨过多个较短区间，ed 会保留这段已经覆盖到的最远右端。每轮合并只连接已经相交的范围，分离时又不跨过空隙，所以最终覆盖恰好等于原并集。

循环只会在遇到下一段时写出上一段。扫描结束后，当前维护的最后一段还未写出，必须再追加一次。

解题步骤

  1. 原地按左端点升序排列区间，取第一段初始化 st 和 ed。
  2. 从第二段开始扫描，比较新区间左端 s 与当前右端 ed。
  3. 若 ed < s，先保存当前段，再重置为新区间；否则将右端更新为两者较大值。
  4. 扫描结束后追加最后一段，并返回答案。

左端相同的区间不需要再按右端排序，逐次取最大右端即可。只有一个区间时，主循环不执行，最后追加的就是原区间。闭区间相接时 ed == s，必须走合并分支。

代码实现

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int st = intervals[0][0];
        int ed = intervals[0][1];
        List<int[]> answer = new ArrayList<>();

        for (int i = 1; i < intervals.length; ++i) {
            int s = intervals[i][0];
            int e = intervals[i][1];

            if (ed < s) {
                answer.add(new int[] {
                    st,
                    ed
                });
                st = s;
                ed = e;
            } else {
                ed = Math.max(ed, e);
            }
        }

        answer.add(new int[] {
            st,
            ed
        });

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

import (
    "sort"
)

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    st, ed := intervals[0][0], intervals[0][1]
    var answer [][]int
    for _, e := range intervals[1:] {
        if ed < e[0] {
            answer = append(answer, []int{
                st,
                ed,
            })
            st, ed = e[0], e[1]
        } else if ed < e[1] {
            ed = e[1]
        }
    }
    answer = append(answer, []int{
        st,
        ed,
    })
    return answer
}

复杂度分析

  • 时间复杂度：$O(n\log n)$，排序占主要开销，后续只扫描一次。
  • 空间复杂度：总空间上界为 $O(n)$，结果最多有 $n$ 段。Java 的对象数组排序工作区与临时结果列表也可能占线性空间；Go 排序的辅助空间按库实现计算，扫描本身只使用常数状态。

关键点总结

[!green]

  • 按左端排序使“当前段已经结束”成为可以立即确认的事实，后续不必回头。
  • 当前状态表示一整组合并区间，右端只扩大、不缩小。
  • 相交时继续扩展，分离时结算，最后再补一次收尾。

易错点总结

[!yellow]

  • 用 ed <= s 判断分离，会把共享端点的闭区间拆开。
  • 只与前一个原区间比较，会漏掉更早长区间延伸过来的覆盖。
  • 用新区间右端直接覆盖 ed，会错误缩短包含关系下的合并段。
  • 重置状态前没有保存上一段，或循环结束后漏掉最后一段。

相似题目

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