当前位置：首页 > news >正文

Java实现区间合并算法详解

news 2025/5/3 11:53:32

文章目录

- 一、问题描述
- 二、解决思路
- 三、完整代码实现
- 四、关键代码解析
- - 1. 区间排序逻辑
  - 2. 合并重叠区间
  - 3. 列表转数组
- 五、复杂度分析
- 六、总结

本文重点：本文通过Java代码实现经典的 区间合并算法，详细解析排序、合并逻辑及关键代码片段，帮助读者掌握处理重叠区间问题的核心思路。

一、问题描述

给定一组区间 intervals，其中每个区间表示为 [start_i, end_i]，要求合并所有重叠的区间，并返回一个不重叠的区间数组，且这些区间需要覆盖所有原始区间。

示例：

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

二、解决思路

合并重叠区间的核心步骤可分为以下两步：

按起始点排序
将区间按起始点从小到大排序，确保遍历时只需关注相邻区间是否重叠。
线性扫描合并
维护一个合并后的区间列表，依次将每个区间与列表最后一个区间比较：
- 若当前区间与前一个区间重叠，合并它们（更新结束点）。
- 若不重叠，直接加入列表。

三、完整代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Solution {public int[][] merge(int[][] intervals) {if (intervals == null || intervals.length == 0) {return new int[0][];}// 1. 按区间起始点排序Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));List<int[]> merged = new ArrayList<>();merged.add(intervals[0]);// 2. 合并重叠区间for (int i = 1; i < intervals.length; i++) {int[] last = merged.get(merged.size() - 1);int[] current = intervals[i];if (current[0] <= last[1]) {// 合并区间，更新结束点last[1] = Math.max(last[1], current[1]);} else {merged.add(current);}}// 3. 转换List到二维数组return merged.toArray(new int[merged.size()][]);}
}

四、关键代码解析

1. 区间排序逻辑

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

作用：按区间的起始点（start）升序排序。
示例：
排序前：[[3,5], [1,2], [4,7]] → 排序后：[[1,2], [3,5], [4,7]]。
为什么需要排序？
排序后，所有区间按起始点有序排列，只需比较相邻区间即可判断是否重叠，无需回溯。

2. 合并重叠区间

if (current[0] <= last[1]) {last[1] = Math.max(last[1], current[1]);
} else {merged.add(current);
}

逻辑：
- 当前区间的起始点（current[0]）如果小于等于合并列表中最后一个区间的结束点（last[1]），说明两个区间重叠，合并后的结束点取二者的较大值。
- 否则，直接将当前区间加入列表。

3. 列表转数组

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

作用：将 List<int[]> 转换为 int[][]。
参数意义：
传入 new int[merged.size()][] 是为了指定返回数组的类型为 int[][]。实际返回的数组长度由列表大小决定，传入的数组仅作为类型标记。

五、复杂度分析

时间复杂度：
- 排序：O(n log n)，Arrays.sort 使用快速排序。
- 合并：O(n)，线性遍历一次。
  总时间复杂度：O(n log n)。
空间复杂度：
- 存储合并结果：O(n)（最坏情况下无重叠区间）。
- 排序的栈空间：O(log n)。
  总空间复杂度：O(n)。