力扣56
https://leetcode-cn.com/problems/merge-intervals/
给出一个区间的集合，请合并所有重叠的区间。
示例1
1
2
3
| 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
|
示例 2:
1
2
3
| 输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
|
思路1：按左端点升序排序，推荐这样做，因为这样比较省事。排序后遍历，后一个的开始<=前一个的结束，说明有交集，合并（合并细节：因为一直往后遍历，因此只需要将后一个区间的左端点改为前一个区间的左端点，右端点改为较大的那个）
如：[1, 3], [2, 4] => [1, 3], [1, 4]，可以看到前一个其实是不需要管的，后一个的左端点变成了前一个的左端点，右端点是4>3所以是4，这样实现了“合并”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
Arrays.sort(intervals, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
for (int i = 1; i < intervals.length; i++) {
if (intervals[i - 1][1] >= intervals[i][0]){
intervals[i][0] = intervals[i - 1][0];
intervals[i][1] = Math.max(intervals[i - 1][1], intervals[i][1]);
}else {
res.add(intervals[i - 1]);
}
}
res.add(intervals[intervals.length - 1]);
return res.toArray(new int[0][]);
}
|
思路2：数轴法，其实这个也好想，甚至比思路1先想到（因为说到区间合并会先想到数轴），因此我们可以模拟数轴，进行区间染色：区间头部为2，后面为1，如[1,3]为[0,2,1,1,…]
这里要注意两点：
- 数轴是无限大的，我们模拟数轴只模拟稍微大一点的数就行：int[] flag = new int[10005];
- 要注意区分头部（2）和尾部（1），不能为同样的标识，否则两个不同的区间容易混淆
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
| public int[][] merge(int[][] intervals) {
if (intervals.length == 0 || intervals[0].length == 0){
return intervals;
}
int[] flag = new int[10005];
int max = intervals[0][1];
for (int[] interval : intervals) {
int j = interval[0];
if (flag[j] == 0) {
flag[j] = 2;
}
while (++j <= interval[1]) {
flag[j] = 1;
}
max = Math.max(interval[1], max);
}
boolean border = true;
int index = 0;
List<int[]> res = new ArrayList<>();
int[] a = new int[2];
while (index <= max + 1){
if ((flag[index] == 0 || flag[index] == 2) && !border){
a[1] = index - 1;
res.add(Arrays.copyOf(a, a.length));
border = true;
}
if (flag[index] == 2 && border){
a[0] = index;
border = false;
}
index++;
}
return res.toArray(new int[0][]);
}
|
其他排序的题目点击这里
