Leetcode 56- 合并区间
1. 题目描述
给出一个区间的集合，请合并所有重叠的区间。1
2
3
4
5
6
7
8
9
10示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例?2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
2. 思路
因为是区间，有左右两个值，再加上肯定会涉及到区间之间比大小，于是我立马考虑到，此题可能是滑动双指针的思想。
首先，对每个区间，按照区间左侧的值进行一个排序（升序），然后设定双指针的初始值，再一个一个枚举剩下的区间，和双指针left和right进行比较。两个区间之间的关系大致有下面三种情况：
3. 代码
Java 实现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
88import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
* @ClassName MergeIntervals56
* @Deacription // TODO
* @Author LiuZhian
* @Date 2019-11-03 16:18
* @Version 1.0
**/
public class MergeIntervals56 {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][0];
// 先对区间按左侧值排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
List<int[]> resList = new ArrayList<>();
int left = intervals[0][0];
int right = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
// 共有下面几种情况:
// 1.完全重叠(或子集情况) 啥也不用做
// 2.有交集
// 3.没有交集
// 但是这两种情况都可以泛化成同一操作
// if (intervals[i][0] >= left && intervals[i][1] <= right)
// pass
if (intervals[i][0] <= right && intervals[i][1] >= right)
right = intervals[i][1];
if (intervals[i][0] > right) {
int[] tmp = new int[2];
tmp[0] = left;
tmp[1] = right;
resList.add(tmp);
// 修改当前left right 值
left = intervals[i][0];
right = intervals[i][1];
}
}
// 把最后一个加入结果中
int[] tmp = new int[2];
tmp[0] = left;
tmp[1] = right;
resList.add(tmp);
// 把ArrayList转为二维数组
int n_size = resList.size();
int idx = 0;
int[][] res = new int[n_size][2];
for (int[] item : resList) {
res[idx][0] = item[0];
res[idx][1] = item[1];
idx++;
}
return res;
}
public static void main(String[] args) {
MergeIntervals56 m = new MergeIntervals56();
// int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
int[][] intervals = {{1, 4}, {4, 5}};
int[][] res = m.merge(intervals);
System.out.print("[");
for (int i = 0; i < res.length; i++) {
System.out.print("[" + res[i][0] + "," + res[i][1] + "],");
}
System.out.print("]");
}
}
