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