Java合并区间通常用于处理可能重叠或相邻的区间集合，核心思路为先按区间起始位置排序，再遍历合并，具体步骤：1. 将区间列表按起始值升序排序；2. 初始化结果列表，加入第一个区间；3. 遍历后续区间，若当前区间起始值小于等于结果列表最后一个区间的结束值，则合并（更新结束值为两者最大值），否则直接加入结果集，最终得到一组不重叠的区间，此方法适用于日程安排、时间线处理等场景，通过排序和线性遍历实现高效合并，时间复杂度主要由排序决定，为O(n log n)。
Java合并区间算法详解：问题分析与代码实现
引言：什么是区间合并？
在数据处理、算法设计和实际业务场景中，"区间"是一个常见概念，例如时间段的安排、数值范围的合并、地理区域的叠加等。区间合并（Interval Merging）是指将一组重叠或相邻的区间合并为尽可能少的、不重叠的区间集合，例如给定区间列表 [[1,3],[2,6],[8,10],[15,18]]，合并后应为 [[1,6],[8,10],[15,18]]，[1,3] 和 [2,6] 因重叠合并为 [1,6]；而 [[1,4],[4,5]] 因相邻关系也可合并为 [[1,5]]。
区间合并的核心目标是消除冗余区间，简化数据结构，便于后续的查询、计算或展示，本文将结合Java语言，从问题分析、算法思路到代码实现，深入讲解如何高效实现区间合并,并探讨其优化策略。
问题定义与场景分析
1 区间合并的数学定义
假设有一个区间集合 intervals = [[a₁, b₁], [a₂, b₂], ..., [aₙ, bₙ]]，aᵢ ≤ bᵢ（区间左端点不大于右端点），合并后的区间集合 merged 需满足：
- 无重叠性：对于
merged中任意两个区间[x₁, y₁]和[x₂, y₂]（x₁ ≤ x₂），有y₁ < x₂； - 覆盖完整性：
intervals中的每个区间都包含在merged的某个区间中； - 最小化原则：
merged中的区间数量最少。
2 典型应用场景
- 日程安排：合并重叠的会议时间段,避免资源冲突；
- 数据去重：合并连续的数值范围,减少存储空间；
- 图像处理：合并相邻的像素区域,简化图像分割结果；
- 网络路由：合并重叠的IP地址段,优化路由表；
- 金融分析：合并连续的交易时段,生成活跃时间段报告。
算法思路：排序+遍历合并
区间合并的核心思路可概括为"排序后合并",具体步骤如下：
1 排序：按区间左端点升序排列
将所有区间按照左端点 aᵢ 从小到大排序，排序后，重叠或相邻的区间必然在列表中连续分布，避免了全量两两比较的复杂操作（时间复杂度从 O(n²) 降至 O(n log n)）,排序是算法高效的关键前提。
2 遍历合并：维护当前合并区间
初始化一个合并结果列表 merged，并设置当前合并区间 [currentStart, currentEnd]（初始为第一个区间）,从第二个区间开始遍历：
- 若当前区间的左端点
aᵢ≤currentEnd，说明与当前合并区间重叠或相邻，更新currentEnd = max(currentEnd, bᵢ)（合并后的右端点取两者最大值）； - 若
aᵢ>currentEnd，说明与当前合并区间无重叠，将[currentStart, currentEnd]加入merged，并更新currentStart = aᵢ、currentEnd = bᵢ为新区间。
遍历结束后，将最后一个 [currentStart, currentEnd] 加入 merged，即为最终结果，该算法时间复杂度为 O(n log n)（排序主导），空间复杂度为 O(n)（存储结果）。
Java代码实现
1 定义区间类
定义一个 Interval 类表示区间，包含 start 和 end 属性，以及必要的构造方法和 getter/setter 方法：
public class Interval {
private int start;
private int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public int getStart() {
return start;
}
public void setStart(int start) {
this.start = start;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
@Override
public String toString() {
return "[" + start + "," + end + "]";
}
2 合并区间核心方法
实现 mergeIntervals 方法，输入一个 Interval 列表,返回合并后的列表：
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List;public class IntervalMerger {
public List<Interval> mergeIntervals(List<Interval> intervals) { // 边界条件处理 if (intervals == null || intervals.isEmpty()) { return new ArrayList<>(); } // 按区间左端点排序 Collections.sort(intervals, Comparator.comparingInt(Interval::getStart)); List<Interval> merged = new ArrayList<>(); Interval current = intervals.get(0); for (int i = 1; i < intervals.size(); i++) { Interval next = intervals.get(i); // 检查重叠或相邻 if (next.getStart() <= current.getEnd()) { // 合并区间，取较大右端点 current.setEnd(Math.max(current.getEnd(), next.getEnd())); } else { // 无重叠，添加当前区间并重置 merged.add(current); current = next; } } // 添加最后一个合并区间 merged.add(current); return merged; }
3 测试用例与结果展示
public class Main {
public static void main(String[] args) {
IntervalMerger merger = new IntervalMerger();
// 测试用例1：重叠区间
List<Interval> intervals1 = new ArrayList<>();
intervals1.add(new Interval(1, 3));
intervals1.add(new Interval(2, 6));
intervals1.add(new Interval(8, 10));
intervals1.add(new Interval(15, 18));
System.out.println("原始区间: " + intervals1);
List<Interval> merged1 = merger.mergeIntervals(intervals1);
System.out.println("合并结果: " + merged1);
// 输出: [[1,6],[8,10],[15,18]]
// 测试用例2：相邻区间
List<Interval> intervals2 = new ArrayList<>();
intervals2.add(new Interval(1, 4));
intervals2.add(new Interval(4, 5));
intervals2.add(new Interval(6, 7));
