给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
题解思路
先对二维数组按区间左端点大小排序，然后依次入栈 若栈内区间右端点小于当前区间左端点，则两个区间无重叠部分，直接将当前区间入栈 若栈内区间右端点大于当前区间左端点，则说明两区间存在重叠部分，更新栈内区间右端点值，取最大
实现代码
class Solution {
public int[][] merge(int[][] intervals
) {
if(intervals
.length
== 0){
return new int[0][2];
}
Arrays
.sort(intervals
, new Comparator<int[]>(){
public int compare(int[] o1
, int[] o2
){
return o1
[0] - o2
[0];
}
});
Deque
<int[]> stack
= new LinkedList<>();
for(int[] i
: intervals
){
int[] j
= stack
.peek();
if(stack
.isEmpty() || j
[1] < i
[0]) {
stack
.push(i
);
}else {
j
[1] = Math
.max(j
[1], i
[1]);
}
}
int[][] res
= new int[stack
.size()][2];
for(int i
= stack
.size() - 1; i
>= 0; i
--) {
res
[i
] = stack
.pop();
}
return res
;
}
}
leetcode题目链接
56. 合并区间
