（LeetCodeHot100）56. 合并区间——merge-intervals

56. 合并区间——merge-intervals

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

示例 1：

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

示例 2：

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

示例 3：

1
2
3
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

官方解答

方法一：排序

思路

如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。如下图所示，标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间，它们在排完序的列表中是连续的：

56-2.png
{:align=”center”}

算法

我们用数组 merged 存储最终的答案。

首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

  • 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；（因为已经排过序了→如果下一个的区间的最小值大于右端点，就是一个新的区间了）
  • 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

正确性证明

上述算法的正确性可以用反证法来证明：在排完序后的数组中，两个本应合并的区间没能被合并，那么说明存在这样的三元组 (i,j,k) 以及数组中的三个区间 a[i],a[j],a[k] 满足 i<j<k 并且 (a[i],a[k]) 可以合并，但 (a[i],a[j]) 和 (a[j],a[k]) 不能合并。这说明它们满足下面的不等式：

a[i].end<a[j].start(a[i] 和 a[j] 不能合并)a[j].end<a[k].start(a[j] 和 a[k] 不能合并)a[i].end≥a[k].start(a[i] 和 a[k] 可以合并)

我们联立这些不等式（注意还有一个显然的不等式 a[j].start≤a[j].e*n*d），可以得到：

a[i].end<a[j].start≤a[j].end<a[k].start

产生了矛盾！这说明假设是不成立的。因此，所有能够合并的区间都必然是连续的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            // 这里的L和R是新获取到的
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

复杂度分析

  • 时间复杂度：O(nlogn)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O(nlogn)。
  • 空间复杂度：O(logn)，其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn) 即为排序所需要的空间复杂度。

1. 核心方法：Arrays.sort(...)

Arrays 是 Java 提供的数组工具类，sort() 方法用于对数组排序，这里是它的 重载版本（专门用于排序「对象数组」，二维数组本质是 “一维数组的数组”，属于对象数组），语法格式：

1
Arrays.sort(要排序的数组, 排序规则);
  • 第一个参数 intervals：要排序的二维数组（比如 int[][] intervals）；
  • 第二个参数：一个「比较器（Comparator）」，用于定义 “按什么规则排序”。

2. 排序规则：new Comparator<int[]>() { ... }

这是创建一个 匿名内部类（临时实现 Comparator 接口，不用单独写一个类），Comparator 接口的核心是 compare() 方法 —— 它定义了 “两个元素如何比较大小”，从而决定排序顺序。

  • Comparator<int[]> 中的 <int[]>：泛型参数，表示要比较的 “单个元素” 是 int[] 类型（因为 intervals 是二维数组，每个元素都是一维数组 int[]）；
  • 重写 compare(int[] interval1, int[] interval2) 方法：接收两个要比较的元素（interval1 和 interval2，即二维数组中的两行），返回一个 int 类型的结果，结果的正负 / 零决定了两个元素的顺序：
compare() 返回值 排序规则 通俗理解
负数（< 0） interval1 排在 interval2 前面 interval1 更小
零（= 0） 两者顺序不变 两者相等
正数（> 0） interval1 排在 interval2 后面 interval1 更大

3. 比较逻辑：return interval1[0] - interval2[0]

这是最关键的部分，定义了 “按什么维度排序”：

  • interval1[0]：第一个要比较的行（interval1）的第 1 列元素（索引为 0）；
  • interval2[0]：第二个要比较的行（interval2）的第 1 列元素；
  • 相减的结果直接决定排序：
    • 若 interval1[0] < interval2[0]（比如 1 - 2 = -1）：返回负数，interval1 排前面（升序）；
    • 若 interval1[0] == interval2[0]（比如 2 - 2 = 0）：返回 0，顺序不变；
    • 若 interval1[0] > interval2[0]（比如 3 - 2 = 1）：返回正数，interval1 排后面。

👉 一句话总结：按二维数组每行的第 1 列元素，从小到大排序。