题目描述
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 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 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
解题思路
代码实现
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
| public class Solution56Case1 {
public static int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (o1, o2) -> {
if (o1[0] > o2[0]) {
return 1;
} else if (o1[0] == o2[0]){
return 0;
} else {
return -1;
}
});
List<int[]> result = new ArrayList<>();
result.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] last = result.get(result.size() - 1);
if (last[1] < intervals[i][0]) {
result.add(intervals[i]);
} else {
if (last[1] < intervals[i][1]) {
last[1] = intervals[i][1];
}
}
}
return result.toArray(new int[result.size()][]);
}
public static void main(String[] args) {
int[][] intervals = {{1, 3}, {2, 6}, {18, 20}, {15, 18}};
int[][] merge = merge(intervals);
System.err.println(merge);
}
}
|