Interval List Intersections
给两个intervals, 返回重叠的intervals.
这个题我用的是linear scan, 也是和前边的interval的题一样, 通过设置open和close来把A和B放到一起, 然后通过一个变量balance来track open和close的先后, 通过判断得知, 当balance等于2, 并且当前是close的时候, 即使重叠的部分.
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
int open = 1;
int close = -1;
int[][] ary = new int[(A.length + B.length) * 2][2];
int i = 0;
for(int[] a : A) {
ary[i][0] = a[0];
ary[i][1] = open;
i++;
ary[i][0] = a[1];
ary[i][1] = close;
i++;
}
for(int[] b : B) {
ary[i][0] = b[0];
ary[i][1] = open;
i++;
ary[i][0] = b[1];
ary[i][1] = close;
i++;
}
Arrays.sort(ary, (a,b) -> (a[0] == b[0] ? b[1] - a[1]: a[0] - b[0]));
int balance = 0;
List<int[]> list = new ArrayList<>();
for(int j = 0; j < ary.length; j++) {
if(balance == 2 && ary[j][1] == close)
list.add(new int[]{ary[j-1][0], ary[j][0]});
balance += ary[j][1];
}
int[][] res = new int[list.size()][2];
for(int k = 0 ; k < list.size(); k++) {
res[k] = list.get(k);
}
return res;
}
}