Hot 100 --- 合并区间

本文概览：本文以LeetCode经典题目"合并区间"为例，从暴力解法入手，分析其必须遍历全部剩余数组的原因，再通过排序将"未知"变为"已知"，系统讲解如何利用排序后天然满足的重叠判断条件，将时间复杂度从 O(n²) 优化到 O(n log n)

一、题目

合并区间题目

二、题目分析

给定一个区间的集合 intervals，其中 intervals[i] = [start, end]，合并所有重叠的区间，返回一个不重叠的区间数组

目标：将所有有重叠的区间合并，返回合并后的区间集合

核心问题：如何判断两个区间是否重叠，以及如何高效地找到所有需要合并的区间

思路概览

Java实现代码如下

public int[][] merge(int[][] intervals) {
    // 空值校验
    if (intervals == null || intervals.length == 0) {
        return new int[0][];
    }

    // 按照起点排序
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    // 合并区间
    List<int[]> merged = new ArrayList<>();
    // 当前区间
    int[] current = intervals[0];

    // 遍历剩余区间
    for (int i = 1; i < intervals.length; i++) {
        int[] next = intervals[i];
        // 如果当前区间和下一个区间重叠，合并它们
        if (current[1] >= next[0]) {
            current[1] = Math.max(current[1], next[1]);
        } else {
            // 否则，将当前区间添加到结果列表中，并更新当前区间为下一个区间
            merged.add(current);
            current = next;
        }
    }
    // 添加最后一个区间
    merged.add(current);
    // 将结果列表转换为二维数组并返回
    return merged.toArray(new int[merged.size()][]);
}

思路简要说明

按起点排序：将区间按照 start 升序排序，排序后相邻区间才可能重叠
逐个合并：维护一个当前区间 current，遍历剩余区间，如果与当前区间重叠则合并（更新 end 为两者的较大值），否则将当前区间加入结果，开始新的区间
重叠判断：排序后只需判断 current[1] >= next[0]，即当前区间的 end 是否大于等于下一个区间的 start

三、思路详解

暴力解法入手

最自然的想法是：对于每个区间，都去检查剩余区间中有没有和自己重叠的，如果有就合并。但问题是，合并之后产生的新区间可能又和别的区间重叠，又需要重新检查

更具体地说，暴力做法是：每次取一个区间，遍历剩余所有区间找重叠，合并后得到一个更大的区间，然后再用这个新区间继续遍历剩余区间，直到没有新的重叠为止。然后对下一个未合并的区间重复同样的过程

显然可以得出以下结论

时间复杂度：O(n²)，每个区间都可能需要遍历剩余所有区间
核心瓶颈：因为数组无序，对于每个区间，我们不知道剩余区间里有没有和自己重叠的，所以只能全部检查一遍。而且合并后产生的新区间又可能和别的区间重叠，还需要重新扫描
关键思考：如果数组是有序的，我们就不需要遍历完了——只需要顺序遍历下去，自然就能知道后面还有没有重叠的区间。一旦发现不重叠，就可以直接跳过当前区间，去看下一个区间有没有重叠，不需要再回头扫描

排序 + 合并解法

思路分析

暴力解法之所以需要反复扫描，根本原因是数组无序——我们不知道后面的区间和当前区间是什么关系，只能逐个检查。那我们能不能通过排序，让重叠的区间"靠在一起"，这样就不需要每次都扫描全部了？

考虑两个区间重叠的条件：前面区间的 end >= 后面区间的 start。也就是说，如果两个区间重叠，那么前面区间的起点必然小于等于后面区间的起点，同时前面区间的终点要大于等于后面区间的起点

如果我们按照 start 升序排序，那么排序后的数组天然满足了一个条件：前面区间的 start 一定小于等于后面区间的 start。这样，两个区间是否重叠就只需要看一个条件：前面区间的 end 是否 >= 后面区间的 start

如果按 end 排序呢？也可以，但需要逆向思考——从后往前看，判断后面区间的 start 是否 <= 前面区间的 end，逻辑上是等价的，但不如按 start 排序后从前往后遍历来得直观，所以尽量选择正向的按 start 排序

排序后为什么不需要回看？

按 start 排序后，我们只需要从左往右遍历，维护一个当前区间 current：

如果 current[1] >= next[0]，说明重叠，合并（更新 end 为较大值）
如果 current[1] < next[0]，说明不重叠，当前区间不可能再和后面的任何区间重叠了（因为后面的 start 更大），所以可以把当前区间加入结果，开始处理下一个区间

这就是排序带来的关键优势：一旦当前区间和下一个区间不重叠，就可以确定当前区间已经处理完毕，不需要再回头看

举例说明

以 intervals = [[1,3],[2,6],[8,10],[15,18]] 为例（已排序）

步骤	current	next	current[1] >= next[0]?	操作	current（更新后）
初始	[1,3]	-	-	-	[1,3]
1	[1,3]	[2,6]	3 >= 2，重叠	合并，end=max(3,6)=6	[1,6]
2	[1,6]	[8,10]	6 < 8，不重叠	加入[1,6]，current=[8,10]	[8,10]
3	[8,10]	[15,18]	10 < 15，不重叠	加入[8,10]，current=[15,18]	[15,18]
结束	[15,18]	-	-	加入[15,18]	-