Interval List Intersections

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

 

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

 

Note:

  1. 0 <= A.length < 1000
  2. 0 <= B.length < 1000
  3. 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

Solution1:

sort

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        int[][] combined = new int[A.length + B.length][2];
        int i = 0;
        for (int[] interval : A) {
            combined[i ++] = interval;
        }
        for (int[] interval : B) {
            combined[i ++] = interval;
        }
        if (combined.length == 0) return combined;
        Arrays.sort(combined, (a, b) -> { return Integer.compare(a[0], b[0]) == 0 ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]); });
        for (int[] a : combined) System.out.print(Arrays.toString(a));
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> { return Integer.compare(b[1], a[1]); });
        pq.offer(combined[0]);
        List<int[]> result = new ArrayList();
        for (int j = 1; j < combined.length; j ++) {
            int[] prev = pq.peek();
            int[] curr = combined[j];
            if (curr[0] <= prev[1]) {
                result.add(new int[]{curr[0], Math.min(curr[1], prev[1])});
            }
            pq.offer(curr);
        }
        int[][] r = new int[result.size()][2];
        i = 0;
        for (int[] interval : result) {
            r[i ++] = interval;
        }
        return r;
    }
}

Solution2:

Two pointer

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        if(A == null || A.length == 0 || B == null || B.length == 0)
        return new int[][]{};
        List<int[]> res = new ArrayList<>();
    
        int i = 0, j = 0;
        int startMax, endMin;
        while (i < A.length && j < B.length) {
            startMax = Math.max(A[i][0], B[j][0]);
            endMin = Math.min(A[i][1], B[j][1]);
            
            if (startMax <= endMin) {
                res.add(new int[]{startMax, endMin});
            }
            
            if (endMin == A[i][1]) i ++;
            if (endMin == B[j][1]) j ++;
        }
        return res.toArray(new int[0][2]);
    }
}

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        List<int[]> result = new ArrayList();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            int[] a = A[i];
            int[] b = B[j];
            if (a[1] < b[0]) {
                i ++;
            } else if (b[1] < a[0]) {
                j ++;
            } else {
                int[] inter = new int[]{Math.max(a[0], b[0]), Math.min(a[1], b[1])};
                result.add(inter);
                if (a[1] < b[1]) {
                    i ++;
                } else {
                    j ++;
                }
            }
        }
        int[][] res = new int[result.size()][2];
        for (int k = 0; k < result.size(); k ++) {
            res[k] = result.get(k);
        }
        return res;
    }
}