1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class MergeIntervals {
public int[][] merge(int[][] intervals) {
/**
* 合并所有重叠的区间
*
* @param intervals 区间数组，每个区间表示为 [start, end]
* @return 合并后的不重叠区间数组
*/
// 如果区间数组为空或只有一个区间，直接返回
if (intervals == null || intervals.length <= 1) {
return intervals;
}
// 1. 按照区间的起始位置进行排序
// 使用Comparator比较器，按照每个区间的第一个元素（起始位置）升序排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
// 比较两个区间的起始位置
return Integer.compare(a[0], b[0]);
}
});
// 2. 使用List存储合并后的区间，方便动态添加
List<int[]> result = new ArrayList<>();
// 3. 将第一个区间添加到结果列表中作为起始
result.add(intervals[0]);
// 4. 遍历排序后的区间数组
for (int i = 1; i < intervals.length; i++) {
// 获取当前区间
int[] currentInterval = intervals[i];
// 获取结果列表中最后一个区间（即最近添加的区间）
int[] lastInterval = result.get(result.size() - 1);
// 5. 检查当前区间是否与最后一个区间重叠
// 如果当前区间的起始位置 <= 最后一个区间的结束位置，说明有重叠
if (currentInterval[0] <= lastInterval[1]) {
// 合并区间：更新最后一个区间的结束位置为两者结束位置的较大值
lastInterval[1] = Math.max(lastInterval[1], currentInterval[1]);
} else {
// 如果没有重叠，直接将当前区间添加到结果列表中
result.add(currentInterval);
}
}
// 6. 将List转换为二维数组返回
return result.toArray(new int[result.size()][]);
}
// 辅助方法：打印二维数组
public void printArray(int[][] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print("[" + arr[i][0] + "," + arr[i][1] + "]");
if (i < arr.length - 1) {
System.out.print(",");
}
}
System.out.println("]");
}
// 测试代码
public static void main(String[] args) {
MergeIntervals solution = new MergeIntervals();
// 示例1
int[][] intervals1 = {{1,3}, {2,6}, {8,10}, {15,18}};
System.out.println("输入: intervals = [[1,3],[2,6],[8,10],[15,18]]");
System.out.print("输出: ");
solution.printArray(solution.merge(intervals1)); // 输出: [[1,6],[8,10],[15,18]]
System.out.println("解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].");
// 示例2
int[][] intervals2 = {{1,4}, {4,5}};
System.out.println("\n输入: intervals = [[1,4],[4,5]]");
System.out.print("输出: ");
solution.printArray(solution.merge(intervals2)); // 输出: [[1,5]]
System.out.println("解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间.");
// 示例3
int[][] intervals3 = {{4,7}, {1,4}};
System.out.println("\n输入: intervals = [[4,7],[1,4]]");
System.out.print("输出: ");
solution.printArray(solution.merge(intervals3)); // 输出: [[1,7]]
System.out.println("解释: 区间 [1,4] 和 [4,7] 可被视为重叠区间.");
// 额外测试用例
int[][] intervals4 = {{1,3}, {4,6}, {8,10}, {15,18}};
System.out.println("\n输入: intervals = [[1,3],[4,6],[8,10],[15,18]]");
System.out.print("输出: ");
solution.printArray(solution.merge(intervals4)); // 输出: [[1,3],[4,6],[8,10],[15,18]]
System.out.println("解释: 没有重叠区间，所有区间保持不变.");
int[][] intervals5 = {{1,10}, {2,5}, {6,8}, {9,12}};
System.out.println("\n输入: intervals = [[1,10],[2,5],[6,8],[9,12]]");
System.out.print("输出: ");
solution.printArray(solution.merge(intervals5)); // 输出: [[1,12]]
System.out.println("解释: 所有区间都有重叠，合并为一个大区间.");
}
}
|
