盒子
盒子

56_合并区间_leetcode

给出一个区间的集合,请合并所有重叠的区间

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

题解: 栈+队列 先按首位置进行排序;接下来,如何判断两个区间是否重叠呢?比如 a = [1,4],b = [2,3]
当 a[1] >= b[0] 说明两个区间有重叠.左边位置一定是确定,就是 a[0],而右边位置是 max(a[1], b[1])
所以,我们就能找出整个区间为:[1,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
Stack<int[]> stack = new Stack<>();
for (int[] num : intervals) {
if (stack.isEmpty()) {
stack.push(num);
continue;
}
int[] arr = stack.peek();
// 表示有重合
if (arr[1] >= num[0]) {
int[] combined = {arr[0], Math.max(arr[1], num[1])};
stack.pop();
stack.push(combined);
} else {
stack.push(num);
}
}
return stack.toArray(new int[0][]);
}
}

AC传送门leetcode

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫