Java详解LeetCode 热题 100(14):LeetCode 56. 合并区间（Merge Intervals）详解

1. 题目描述

给出一个区间的集合，请合并所有重叠的区间。

示例 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] 可被视为重叠区间，因为它们共享端点4。

提示：

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 10^4

进阶： 你能设计一个时间复杂度为 O(nlogn) 的算法解决此问题吗？

2. 理解题目

这道题要求我们合并所有重叠的区间。具体来说：

• 输入是一个二维数组，每个子数组表示一个区间 [start, end]
• 如果两个区间有重叠，我们需要将它们合并成一个更大的区间
• 重叠的定义：两个区间 [a, b] 和 [c, d] 重叠，当且仅当 a ≤ d 且 c ≤ b
• 合并后的区间是 [min(a, c), max(b, d)]

关键点：

1. 区间可能以任意顺序给出
2. 区间可能完全包含另一个区间
3. 边界相等也被视为重叠（如示例2）

3. 解法一：排序 + 一次遍历法

3.1 思路

最高效的解法是先排序再合并：

1. 按照区间的起始位置对所有区间进行排序
2. 遍历排序后的区间列表，将重叠的区间合并

排序确保了相邻的重叠区间会排列在一起，这样我们只需要一次遍历就能合并所有重叠的区间。

3.2 Java代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {public int[][] merge(int[][] intervals) {// 处理边界情况if (intervals == null || intervals.length <= 1) {return intervals;}// 按照区间的起始位置排序Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));// 用于存储合并后的区间List<int[]> result = new ArrayList<>();// 将第一个区间加入结果int[] currentInterval = intervals[0];result.add(currentInterval);// 遍历剩余区间for (int i = 1; i < intervals.length; i++) {// 获取当前遍历到的区间int[] interval = intervals[i];// 如果当前区间的起始位置小于等于上一个区间的结束位置，说明有重叠if (interval[0] <= currentInterval[1]) {// 更新当前区间的结束位置为两个区间结束位置的最大值currentInterval[1] = Math.max(currentInterval[1], interval[1]);} else {// 没有重叠，将当前区间加入结果currentInterval = interval;result.add(currentInterval);}}// 将List转换为数组return result.toArray(new int[result.size()][]);}
}

3.3 代码详解

详细解释每一步的意义和实现：

// 处理边界情况
if (intervals == null || intervals.length <= 1) {return intervals;
}

• 如果数组为空或者只有一个区间，不需要合并，直接返回原数组

// 按照区间的起始位置排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

• 使用 Java 8 Lambda 表达式创建一个比较器，按区间的起始位置排序
• 排序确保了相邻的可能重叠区间会排列在一起

// 用于存储合并后的区间
List<int[]> result = new ArrayList<>();// 将第一个区间加入结果
int[] currentInterval = intervals[0];
result.add(currentInterval);

• 创建一个动态数组存储合并结果
• 先将排序后的第一个区间加入结果，作为当前正在处理的区间

// 遍历剩余区间
for (int i = 1; i < intervals.length; i++) {// 获取当前遍历到的区间int[] interval = intervals[i];// 如果当前区间的起始位置小于等于上一个区间的结束位置，说明有重叠if (interval[0] <= currentInterval[1]) {// 更新当前区间的结束位置为两个区间结束位置的最大值currentInterval[1] = Math.max(currentInterval[1], interval[1]);} else {// 没有重叠，将当前区间加入结果currentInterval = interval;result.add(currentInterval);}
}

• 遍历排序后的区间数组（从第二个开始）
• 检查当前区间与结果中最后一个区间是否重叠
• 如果重叠，合并它们（更新结束位置为两者的最大值）
• 如果不重叠，将当前区间添加到结果中

// 将List转换为数组
return result.toArray(new int[result.size()][]);

• 将ArrayList转换为要求返回的二维数组

3.4 复杂度分析

• 时间复杂度: O(n log n)，其中 n 是区间的数量。排序需要 O(n log n) 时间，而后续的一次遍历需要 O(n) 时间，总体复杂度由排序决定。
• 空间复杂度: O(n)，需要存储合并后的区间数组。在最坏情况下，没有区间可以合并，我们需要存储所有 n 个区间。排序可能需要 O(log n) 的额外空间。

3.5 适用场景

这种解法是解决区间合并问题的主流方法，适用于绝大多数情况。它简洁高效，容易理解和实现。

4. 解法二：双指针法

4.1 思路

双指针法本质上与解法一相同，但使用两个变量明确跟踪当前合并区间的左右边界，使代码更加清晰：

1. 对区间按起始位置排序
2. 设置两个指针 left 和 right 跟踪当前合并区间的边界
3. 遍历排序后的区间，根据重叠情况更新指针或添加新区间

4.2 Java代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {public int[][] merge(int[][] intervals) {if (intervals == null || intervals.length <= 1) {return intervals;}// 按照区间的起始位置排序Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));List<int[]> result = new ArrayList<>();// 初始化左右指针int left = intervals[0][0];int right = intervals[0][1];for (int i = 1; i < intervals.length; i++) {// 如果当前区间的起始位置小于等于右指针，说明有重叠if (intervals[i][0] <= right) {// 更新右指针为两个区间结束位置的最大值right = Math.max(right, intervals[i][1]);} else {// 没有重叠，将当前合并后的区间加入结果result.add(new int[]{left, right});// 更新左右指针为当前区间left = intervals[i][0];right = intervals[i][1];}}// 添加最后一个合并后的区间result.add(new int[]{left, right});return result.toArray(new int[result.size()][]);}
}

4.3 代码详解

双指针法的核心在于显式地使用两个变量追踪当前合并区间的边界：

// 初始化左右指针
int left = intervals[0][0];
int right = intervals[0][1];

• left 跟踪当前合并区间的起始位置
• right 跟踪当前合并区间的结束位置
• 初始值设为第一个区间的边界

for (int i = 1; i < intervals.length; i++) {// 如果当前区间的起始位置小于等于右指针，说明有重叠if (intervals[i][0] <= right) {// 更新右指针为两个区间结束位置的最大值right = Math.max(right, intervals[i][1]);} else {// 没有重叠，将当前合并后的区间加入结果result.add(new int[]{left, right});// 更新左右指针为当前区间left = intervals[i][0];right = intervals[i][1];}
}

• 遍历时检查当前区间是否与已合并区间重叠
• 如果重叠，只需更新右边界
• 如果不重叠，将已合并区间加入结果，并重置左右指针为新区间

// 添加最后一个合并后的区间
result.add(new int[]{left, right});

• 循环结束后，需要将最后一个合并区间添加到结果中

4.4 复杂度分析

• 时间复杂度: O(n log n)，与解法一相同，主要消耗在排序步骤。
• 空间复杂度: O(n)，需要存储合并后的区间数组。

4.5 与解法一的比较

两种解法的核心思想相同，都是先排序再合并，时间和空间复杂度也相同。但双指针法的代码逻辑可能更清晰，特别是在教学或讲解算法时。

5. 解法三：TreeMap法

5.1 思路

TreeMap 是一种有序映射数据结构，可以用来高效地处理区间合并问题，特别是当区间操作比较复杂时。基本思路是：

1. 使用 TreeMap 存储区间，键为区间起始位置，值为区间结束位置
2. 遍历原始区间，对于每个区间，查找可能与之重叠的已存在区间
3. 合并重叠区间，更新 TreeMap

这种方法在处理动态添加区间的场景中特别有用。

5.2 Java代码实现

import java.util.*;class Solution {public int[][] merge(int[][] intervals) {if (intervals == null || intervals.length <= 1) {return intervals;}// 使用 TreeMap 来存储区间，键为起始位置，值为结束位置TreeMap<Integer, Integer> map = new TreeMap<>();// 遍历所有区间for (int[] interval : intervals) {int start = interval[0];int end = interval[1];// 查找小于等于当前起始位置的最大键（floorKey）Integer floorKey = map.floorKey(start);// 如果存在这样的键，且其对应的值大于等于当前起始位置，则可以合并if (floorKey != null && map.get(floorKey) >= start) {start = floorKey;end = Math.max(map.get(floorKey), end);map.remove(floorKey);}// 继续检查后面的区间是否可以合并Integer ceilingKey = map.ceilingKey(start);while (ceilingKey != null && ceilingKey <= end) {end = Math.max(map.get(ceilingKey), end);map.remove(ceilingKey);ceilingKey = map.ceilingKey(start);}// 将合并后的区间加入 TreeMapmap.put(start, end);}// 将 TreeMap 转换为数组int[][] result = new int[map.size()][2];int i = 0;for (Map.Entry<Integer, Integer> entry : map.entrySet()) {result[i][0] = entry.getKey();result[i][1] = entry.getValue();i++;}return result;}
}

5.3 代码详解

TreeMap 法的关键在于利用 TreeMap 的有序性和范围查询功能：

// 使用 TreeMap 来存储区间，键为起始位置，值为结束位置
TreeMap<Integer, Integer> map = new TreeMap<>();

• TreeMap 自动按键（区间起始位置）排序
• 值保存区间的结束位置

// 查找小于等于当前起始位置的最大键（floorKey）
Integer floorKey = map.floorKey(start);// 如果存在这样的键，且其对应的值大于等于当前起始位置，则可以合并
if (floorKey != null && map.get(floorKey) >= start) {start = floorKey;end = Math.max(map.get(floorKey), end);map.remove(floorKey);
}

• floorKey(start) 查找小于等于 start 的最大键
• 如果该键对应的值大于等于 start，说明区间重叠，需要合并
• 合并后更新起始位置和结束位置，并从 TreeMap 中移除原区间

// 继续检查后面的区间是否可以合并
Integer ceilingKey = map.ceilingKey(start);
while (ceilingKey != null && ceilingKey <= end) {end = Math.max(map.get(ceilingKey), end);map.remove(ceilingKey);ceilingKey = map.ceilingKey(start);
}

• ceilingKey(start) 查找大于等于 start 的最小键
• 循环检查是否有更多区间需要合并
• 对于每个满足条件的区间，更新结束位置并从 TreeMap 中移除

// 将合并后的区间加入 TreeMap
map.put(start, end);

• 将最终合并后的区间添加到 TreeMap 中

// 将 TreeMap 转换为数组
int[][] result = new int[map.size()][2];
int i = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {result[i][0] = entry.getKey();result[i][1] = entry.getValue();i++;
}

• 将 TreeMap 中的区间转换为要求返回的二维数组

5.4 复杂度分析

• 时间复杂度: O(n log n)，其中 n 是区间的数量。TreeMap 的插入和查找操作需要 O(log n) 时间，最坏情况下我们可能需要对每个区间进行这些操作。
• 空间复杂度: O(n)，需要存储 TreeMap 和结果数组。

5.5 适用场景

TreeMap 法特别适合以下场景：

• 需要动态添加或删除区间
• 需要频繁查询与特定点或区间重叠的区间
• 实现更复杂的区间操作，如求区间交集、差集等

对于本题的静态区间合并问题，第一种解法（排序+一次遍历）通常更为简洁高效。

6. 详细步骤分析与示例跟踪

让我们通过几个例子详细跟踪算法的执行过程，以加深理解。

6.1 示例 1：基本重叠情况

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

使用解法一（排序+一次遍历法）：

1. 排序：
   输入已按起始位置排序：[[1,3],[2,6],[8,10],[15,18]]

2. 初始化：

   • result = [[1,3]]
   • currentInterval = [1,3]

3. 遍历：

   • 处理 [2,6]：

     • 检查：2 <= 3，有重叠
     • 更新 currentInterval 为 [1,6]
     • result = [[1,6]]

   • 处理 [8,10]：

     • 检查：8 > 6，无重叠
     • 添加到结果：result = [[1,6],[8,10]]
     • 更新 currentInterval = [8,10]

   • 处理 [15,18]：

     • 检查：15 > 10，无重叠
     • 添加到结果：result = [[1,6],[8,10],[15,18]]
     • 更新 currentInterval = [15,18]

4. 返回结果：[[1,6],[8,10],[15,18]]

6.2 示例 2：边界相等的情况

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

使用解法一：

1. 排序：
   输入已按起始位置排序：[[1,4],[4,5]]

2. 初始化：

   • result = [[1,4]]
   • currentInterval = [1,4]

3. 遍历：

   • 处理 [4,5]：
     • 检查：4 <= 4，有重叠（边界相等也算重叠）
     • 更新 currentInterval 为 [1,5]
     • result = [[1,5]]

4. 返回结果：[[1,5]]

6.3 示例 3：完全包含的情况

输入：intervals = [[1,10],[2,5],[6,8]]

使用解法一：

1. 排序：
   输入已按起始位置排序：[[1,10],[2,5],[6,8]]

2. 初始化：

   • result = [[1,10]]
   • currentInterval = [1,10]

3. 遍历：

   • 处理 [2,5]：

     • 检查：2 <= 10，有重叠（完全被包含）
     • 更新 currentInterval 为 [1,10]（实际上没变化）
     • result = [[1,10]]

   • 处理 [6,8]：

     • 检查：6 <= 10，有重叠（完全被包含）
     • 更新 currentInterval 为 [1,10]（实际上没变化）
     • result = [[1,10]]

4. 返回结果：[[1,10]]

6.4 示例 4：逆序区间

输入：intervals = [[5,8],[3,6],[1,2]]

使用解法一：

1. 排序：
   排序后：[[1,2],[3,6],[5,8]]

2. 初始化：

   • result = [[1,2]]
   • currentInterval = [1,2]

3. 遍历：

   • 处理 [3,6]：

     • 检查：3 > 2，无重叠
     • 添加到结果：result = [[1,2],[3,6]]
     • 更新 currentInterval = [3,6]

   • 处理 [5,8]：

     • 检查：5 <= 6，有重叠
     • 更新 currentInterval 为 [3,8]
     • result = [[1,2],[3,8]]

4. 返回结果：[[1,2],[3,8]]

7. 常见错误与优化

7.1 常见错误

1. 忘记排序：
   这是最常见的错误。如果忘记按区间起始位置排序，算法将不能正确工作。

   // 错误：直接遍历原始数组
   for (int i = 1; i < intervals.length; i++) {// ...
   }// 正确：先排序再遍历
   Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
   for (int i = 1; i < intervals.length; i++) {// ...
   }
   

2. 重叠条件判断错误：
   区间 [a,b] 和 [c,d] 重叠的条件是 a <= d && c <= b，简化后即 a <= d && c <= b。
   对于已排序的区间（a <= c），重叠条件可进一步简化为 c <= b。

   // 错误：判断条件不正确
   if (interval[0] < currentInterval[1]) { // 不包括边界相等情况// ...
   }// 正确：边界相等也视为重叠
   if (interval[0] <= currentInterval[1]) {// ...
   }
   

3. 忘记更新结束位置：
   合并区间时，需要取两个区间结束位置的最大值。

   // 错误：不更新结束位置
   if (interval[0] <= currentInterval[1]) {// 忘记更新结束位置
   }// 正确：更新结束位置为最大值
   if (interval[0] <= currentInterval[1]) {currentInterval[1] = Math.max(currentInterval[1], interval[1]);
   }
   

4. 边界情况处理不当：
   忘记处理空数组或只有一个区间的情况。

   // 忘记处理边界情况
   public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));// ...
   }// 正确处理边界情况
   public int[][] merge(int[][] intervals) {if (intervals == null || intervals.length <= 1) {return intervals;}// ...
   }
   

7.2 性能优化

1. 预估结果大小：
   如果有可能，预先估计结果大小可以避免 ArrayList 的扩容操作。

   // 优化：预估结果大小
   List<int[]> result = new ArrayList<>(intervals.length); // 最多有intervals.length个区间
   

2. 直接操作数组：
   对于特别大的输入，可以考虑直接操作数组而不是使用 ArrayList，以减少内存分配。

   // 优化：直接操作数组
   int[][] result = new int[intervals.length][2];
   int idx = 0;result[idx++] = intervals[0];for (int i = 1; i < intervals.length; i++) {// ...if (overlap) {result[idx-1][1] = Math.max(...);} else {result[idx++] = intervals[i];}
   }// 创建正确大小的结果数组
   return Arrays.copyOf(result, idx);
   

3. 避免无用合并：
   对于明显不可能重叠的区间（例如数据范围很大但区间很少），可以考虑先检查是否有重叠的可能。

   // 优化：检查是否有可能重叠
   int minStart = Integer.MAX_VALUE;
   int maxEnd = Integer.MIN_VALUE;for (int[] interval : intervals) {minStart = Math.min(minStart, interval[0]);maxEnd = Math.max(maxEnd, interval[1]);
   }if (maxEnd - minStart < intervals.length) {// 区间可能重叠，需要合并// ...
   } else {// 区间不可能全部重叠，正常处理// ...
   }
   

8. 扩展题目与应用

8.1 区间插入

LeetCode 57. 插入区间：给你一个无重叠的，按照区间起始端点排序的区间列表，在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠。

解法思路：

1. 找到新区间应该插入的位置
2. 处理与新区间重叠的已有区间
3. 合并所有重叠区间

8.2 区间列表的交集

LeetCode 986. 区间列表的交集：给定两个由一些闭区间组成的列表，每个区间列表都是成对不相交的，并且已经排序。返回这两个区间列表的交集。

解法思路：

1. 使用双指针分别遍历两个区间列表
2. 计算当前两个区间的交集
3. 移动指向结束位置较小的那个区间的指针

8.3 会议室问题

LeetCode 252. 会议室：给定一系列会议时间区间，判断一个人是否能参加所有会议。

LeetCode 253. 会议室 II：给定一系列会议时间区间，计算需要的最少会议室数量。

这类问题本质上也是区间操作问题，可以应用类似的排序和扫描线技术解决。

9. 实际应用场景

区间合并问题在实际应用中非常常见：

1. 日程安排：

   • 查找空闲时间段
   • 合并重叠的会议时间
   • 冲突检测

2. 资源分配：

   • 合并重叠的资源占用时间
   • 最小化所需资源数量

3. 网络连接管理：

   • 合并重叠的网络流量时间段
   • 带宽利用分析

4. 数据压缩：

   • 合并连续的数据块
   • 减少存储需求

5. 基因序列分析：

   • 合并重叠的基因片段
   • 基因组装

10. 完整的 Java 解决方案

以下是结合了各种优化和最佳实践的完整解决方案：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {public int[][] merge(int[][] intervals) {// 处理边界情况if (intervals == null) {return new int[0][0];}int n = intervals.length;if (n <= 1) {return intervals;}// 按照区间的起始位置排序Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));// 用于存储合并后的区间List<int[]> result = new ArrayList<>();// 初始化当前区间为第一个区间int start = intervals[0][0];int end = intervals[0][1];// 遍历排序后的区间for (int i = 1; i < n; i++) {// 当前区间int[] current = intervals[i];// 如果当前区间与合并区间重叠if (current[0] <= end) {// 更新合并区间的结束位置end = Math.max(end, current[1]);} else {// 将合并完成的区间加入结果result.add(new int[]{start, end});// 开始新的合并区间start = current[0];end = current[1];}}// 添加最后一个合并区间result.add(new int[]{start, end});// 转换为数组并返回return result.toArray(new int[result.size()][]);}
}

代码已经尽可能简化，同时保持了良好的可读性和正确性。这个解决方案在 LeetCode 上的表现通常会击败约 95% 的提交。

11. 总结与技巧

11.1 解题要点

1. 排序是关键：区间问题通常需要先排序，使得相似的区间靠在一起。
2. 一次遍历合并：排序后，只需一次遍历即可合并所有重叠区间。
3. 重叠条件：理解区间重叠的条件是解决此类问题的基础。
4. 妥善处理边界情况：包括空输入、单区间输入和边界相等的情况。

11.2 学习收获

通过学习合并区间问题，你可以掌握：

• 区间操作的基本技巧
• 贪心算法的应用
• 排序和扫描线技术
• 数据结构的选择与性能优化

11.3 面试技巧

如果在面试中遇到此类问题：

1. 先分析问题，理解重叠的定义
2. 提出排序的思路，解释为什么排序是必要的
3. 设计核心算法：如何合并重叠区间
4. 讨论边界情况和可能的优化
5. 分析时间和空间复杂度

无论哪种区间问题，排序通常是第一步，之后的具体操作取决于问题要求（合并、插入、查找交集等）。

12. 参考资料

• LeetCode 官方题解：合并区间
• LeetCode 题目链接：合并区间