Interval List Intersections
给两个intervals, 返回重叠的intervals.
这个题我用的是linear scan, 也是和前边的interval的题一样, 通过设置open和close来把A和B放到一起, 然后通过一个变量balance来track open和close的先后, 通过判断得知, 当balance等于2, 并且当前是close的时候, 即使重叠的部分.
|
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 |
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; } } |