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;
    }
}