问题描述
合并区间是算法面试与工程实践中非常经典的区间处理问题。给定一组区间，每个区间由起始位置和结束位置组成，要求将所有存在重叠的区间进行合并，返回合并后的区间列表。例如，给定区间 [[1,3],[2,6],[8,10],[15,18]]，合并后的结果为 [[1,6],[8,10],[15,18]]，因为 [1,3] 与 [2,6] 存在重叠部分。
该问题在实际中有广泛应用，如会议时间冲突检测、日程合并、资源占用区间整合等场景。
核心思路：贪心算法
合并区间的核心思想是贪心策略：
- 排序阶段：首先将所有区间按照起始位置（
start）进行升序排序。如果起始位置相同，则按结束位置（end）升序排序。 - 合并阶段：维护一个当前正在处理的区间
current。依次遍历排序后的区间： - 如果当前区间的起始位置小于等于
current的结束位置，说明两区间重叠，更新current的结束位置为两者中的较大值。 - 如果不重叠，将
current加入结果列表，并将当前区间设为新的current。 - 收尾阶段：遍历结束后，别忘了将最后一个
current加入结果列表。
完整Java实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
* 合并区间问题求解器
* 使用贪心算法：先排序，再逐个合并重叠区间
*/
public class MergeIntervals {
/**
* 表示一个区间对象，包含起始和结束位置
*/
public static class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "[" + start + "," + end + "]";
}
}
/**
* 合并所有重叠区间的主方法
*
* @param intervals 输入的区间数组，每个元素为[start, end]
* @return 合并后的区间列表
*/
public int[][] merge(int[][] intervals) {
// 特殊情况处理：空数组或只有一个区间时直接返回
if (intervals == null || intervals.length <= 1) {
return intervals;
}
// 第一步：按照区间起始位置升序排序
// 如果起始位置相同，则按结束位置升序排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) {
return a[0] - b[0]; // 按起始位置升序
}
return a[1] - b[1]; // 起始相同则按结束位置升序
}
});
// 使用动态数组存储合并结果
List<int[]> merged = new ArrayList<>();
// 初始化当前区间为先排序后的第一个区间
int[] current = intervals[0];
// 第二步：遍历所有区间，进行合并判断
for (int i = 1; i < intervals.length; i++) {
int[] interval = intervals[i];
// 判断当前区间是否与正在合并的区间重叠
// 重叠条件：当前区间的起始位置 <= 正在合并区间的结束位置
if (interval[0] <= current[1]) {
// 存在重叠，扩展当前区间的结束位置
// 取两者结束位置的较大值，确保覆盖合并后的完整范围
current[1] = Math.max(current[1], interval[1]);
} else {
// 不存在重叠，将当前合并完成的区间加入结果
merged.add(new int[]{current[0], current[1]});
// 开始处理新的区间
current = interval;
}
}
// 第三步：别忘了将最后一个区间加入结果
merged.add(new int[]{current[0], current[1]});
// 将List转换为二维数组返回
return merged.toArray(new int[merged.size()][]);
}
/**
* 打印二维数组，方便测试观察结果
*/
private static void printIntervals(int[][] intervals) {
System.out.print("[");
for (int i = 0; i < intervals.length; i++) {
System.out.print("[" + intervals[i][0] + "," + intervals[i][1] + "]");
if (i < intervals.length - 1) {
System.out.print(",");
}
}
System.out.println("]");
}
public static void main(String[] args) {
MergeIntervals solution = new MergeIntervals();
// 测试用例1：基础合并场景
int[][] test1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
System.out.print("输入: ");
printIntervals(test1);
int[][] result1 = solution.merge(test1);
System.out.print("输出: ");
printIntervals(result1);
// 预期输出: [[1,6],[8,10],[15,18]]
// 测试用例2：完全包含的区间
int[][] test2 = {{1, 4}, {4, 5}};
System.out.print("\n输入: ");
printIntervals(test2);
int[][] result2 = solution.merge(test2);
System.out.print("输出: ");
printIntervals(result2);
// 预期输出: [[1,5]]
// 测试用例3：多个重叠区间
int[][] test3 = {{1, 4}, {0, 2}, {3, 5}};
System.out.print("\n输入: ");
printIntervals(test3);
int[][] result3 = solution.merge(test3);
System.out.print("输出: ");
printIntervals(result3);
// 预期输出: [[0,5]]
}
}
复杂度分析
- 时间复杂度：
O(n log n)，其中n为区间数量。排序操作消耗O(n log n)，后续的线性遍历消耗O(n)，总体由排序主导。 - 空间复杂度：
O(n)，用于存储排序后的结果列表。如果允许原地修改输入数组，则空间复杂度可优化至O(1)（不考虑输出数组）。
扩展思考
- 插入新区间：如果需要在已有合并后的区间列表中插入一个新区间，可以使用二分查找定位插入位置，时间复杂度为
O(log n)。 - 区间交集：求多个区间列表的交集，可以使用多指针同步遍历的方法。
- 最大不相交区间数：这是合并区间的反向问题，经典贪心策略是按结束位置排序，选择结束最早的区间。
总结
合并区间通过先排序、后贪心合并的两阶段策略，高效地解决了区间重叠问题。掌握这一思路后，可以举一反三解决大多数区间相关的算法问题。
