56. 合并区间

鲁迅曾说，尽量每天都让自己充实一点，你可以刷一个小时的短视频，打一个小

时的王者荣耀，但尽量再留一个小时出来读一下书、教程、博客，让自己的大脑

保持活跃，而不是垃圾场。如果真的没有事情做，刷 LeetCode 确实是一个不错

的选择。好，今天继续坚持来一道 LeetCode 题解，第 56 题——合并区间。

题意

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [startᵢ, endᵢ] 。

请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所

有区间 。

难度

中等

示例

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]

输出：[[1,6],[8,10],[15,18]]

解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]

输出：[[1,5]]

解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

分析 1

假如区间 A[]、B[] 能够合并，我们让 A[] 的左端点比 B[] 的左端点更靠近 0，那么必然会

有 A[1] >= B[0] 条件成立，也只有这样，两个区间才能够合并。

而合并后的区间，如果还要与其他区间合并，也一定满足上面的条件。

在这个条件的基础上，这道题就迎刃而解了。

我们只需要先按照左端点从小到大给所有的区间排序，然后再从小到大依次合并区间并且

加入答案即可。

class Solution{

public int[][] merge(int[][] intervals) {

// 如果区间为空，直接返回空数组

if(intervals.length == 0){

return new int[0][0];

}

//按左端点大小排序

 Arrays.sort(intervals, new Comparator<int[]>() {

@Override

public int compare(int[] o1, int[] o2) {

return o1[0] - o2[0];

}

});

List<int[]> ans = new ArrayList<>();

// 合并区间

for(int i = 0 ;i < intervals.length;i++){

// 当前区间的左右端点

int lef = intervals[i][0],rig = intervals[i][1];

// 如果当前区间的左端点小于等于上一个区间的右端点，合并区间

while((i + 1 < intervals.length) && intervals[i + 1][0] <= rig){

rig = Math.max(rig,intervals[i + 1][1]);//合并区间

i++;

}

// 加入答案

ans.add(new int[]{lef,rig});

}

// 以数组形式返回答案

return ans.toArray(new int[ans.size()][0]);

}

}

时间复杂度：$ O(n) $。

我们只用了一次排序，然后把相邻的区间依次合并过去，每个区间只会被扫描一次，所以

时间开销并不会很大。

056.合并区间-20250126113627.png

分析 2

也可以用一个 for 循环来搞定。

第一步，仍然是排序区间，按照区间的起始值 start 进行升序排序，这样可以保证区间按

顺序处理，方便合并。

第二步，遍历排序后的区间，用一个变量 currentInterval 表示当前正在合并的区间。

如果当前区间的 start 大于 currentInterval 的 end，说明没有重叠，将 currentInterval 加

入结果，并更新为当前区间。

如果有重叠，则更新 currentInterval 的 end 为两者的最大值。

第三步，遍历结束后，将最后一个 currentInterval 加入结果。

class Solution {

public int[][] merge(int[][] intervals) {

if (intervals.length <= 1) {

return intervals; // 如果区间少于等于 1，直接返回

}

// 按区间的起始值排序

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

// 存储合并后的区间

List<int[]> result = new ArrayList<>();

 // 初始化当前区间为第一个区间

int[] currentInterval = intervals[0];

// 遍历剩余区间

for (int i = 1; i < intervals.length; i++) {

// 如果当前区间和遍历的区间有重叠

if (currentInterval[1] >= intervals[i][0]) {

// 合并区间，更新当前区间的结束值

currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);

} else {

// 没有重叠，将当前区间加入结果，并更新当前区间

result.add(currentInterval);

currentInterval = intervals[i];

}

}

// 将最后一个区间加入结果

result.add(currentInterval);

// 转换结果为二维数组返回

return result.toArray(new int[result.size()][]);

}

public static void main(String[] args) {

Solution solution = new Solution();

int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};

System.out.println(Arrays.deepToString(solution.merge(intervals))); // 输出:

[[1, 6], [8, 10], [15, 18]]

}

}

效率会更高一些。

056.合并区间-20250126114647.png

总结

像类似这种区间合并的问题，上来就先排序，因为排序后，相邻的区间就可以合并了。

再找到合并的条件，也就是左端点小于等于上一个区间的右端点。

其实问题到最后就很 easy 了。

力扣链接：https://leetcode.cn/problems/merge-intervals/