题目意思很好理解：
给定一个区间集合，每个区间由 [start, end] 组成，要求合并所有重叠的区间，返回一个不重叠的区间数组，且这个数组要恰好覆盖输入中的所有区间。
思路
首先，先按每个区间的起始值从小到大排序，这样重叠的区间就会挨在一起，方便后续合并；
然后初始化一个结果列表，把排序后的第一个区间放进去，作为初始的待合并区间；
接着遍历剩下的所有区间，每次取出结果列表的最后一个区间和当前区间比较：
如果当前区间的起始值小于等于最后一个区间的结束值，说明两个区间重叠，就把最后一个区间的结束值更新为两者的最大值，完成合并；
如果不重叠，就直接把当前区间加入结果列表；
最后把结果列表转换成二维数组返回即可。
代码实现
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
|
public int[][] merge(int[][] intervals) {
// 区间个数为0或1，直接返回
if (intervals.length <= 1) {
return intervals;
}
// 1. 按区间的start值从小到大排序
// a[0]-b[0]表示按start升序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// 2. 初始化结果列表，存储合并后的区间
List<int[]> res = new ArrayList<>();
// 先将排序后的第一个区间加入结果列表，作为初始合并区间
res.add(intervals[0]);
// 3. 遍历剩下的所有区间，逐个合并
for (int i = 1; i < intervals.length; i++) {
// 取出结果列表中最后一个区间
int[] last = res.get(res.size() - 1);
// 取出当前遍历的区间
int[] curr = intervals[i];
// 判断是否重叠：当前区间的start <= 最后一个区间的end
if (curr[0] <= last[1]) {
// 重叠：合并区间，更新最后一个区间的end为两者最大值
last[1] = Math.max(last[1], curr[1]);
} else {
// 不重叠：直接将当前区间加入结果列表
res.add(curr);
}
}
// 4. 将List<int[]>转换为int[][]
return res.toArray(new int[res.size()][]);
}
|