-
Notifications
You must be signed in to change notification settings - Fork 1
/
MergeIntervals.java
72 lines (64 loc) · 2.45 KB
/
MergeIntervals.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
package com.hncboy;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
* @author hncboy
* @date 2019/10/6 10:13
* 56.合并区间
*
* 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。
* 请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
*
* 示例 1:
* 输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
* 输出:[[1,6],[8,10],[15,18]]
* 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
*
* 示例 2:
* 输入:intervals = [[1,4],[4,5]]
* 输出:[[1,5]]
* 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
*
* 提示:
* 1 <= intervals.length <= 104
* intervals[i].length == 2
* 0 <= starti <= endi <= 104
* 通过次数 344,050 提交次数 724,795
*
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/merge-intervals
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class MergeIntervals {
public static void main(String[] args) {
int[][] intervals = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
System.out.println(new MergeIntervals().merge(intervals));
}
public int[][] merge(int[][] intervals) {
List<int[]> mergeList = new ArrayList<>();
if (intervals.length == 0) {
return intervals;
}
// 按区间左边界排序
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
mergeList.add(new int[]{intervals[0][0], intervals[0][1]});
// 遍历所有区间
for (int i = 0; i < intervals.length - 1; i++) {
int left1 = mergeList.get(mergeList.size() - 1)[0];
int right1 = mergeList.get(mergeList.size() - 1)[1];
// 获取当前区间
int left2 = intervals[i + 1][0];
int right2 = intervals[i + 1][1];
if (right1 < left2) {
// 情况1:两个区间互不相交,新增一个区间
mergeList.add(new int[]{left2, right2});
} else {
// 情况2:两个区间有相交,在原来区间上修改
mergeList.set(mergeList.size() - 1, new int[]{Math.min(left1, left2), Math.max(right1, right2)});
}
}
return mergeList.toArray(new int[mergeList.size()][2]);
}
}