LeetCode Problem
986. Interval List Intersections
Link to LeetCode
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
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 are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].
Example 1:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Example 2:
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
if (firstList == null || secondList == null) {
return null;
}
if (firstList.length == 0 || secondList.length == 0) {
return new int[0][0];
}
List list = new ArrayList<>();
int i=0, j=0;
while (i< firstList.length && j< secondList.length) {
int []interval = new int[2];
interval[0] = Math.max(firstList[i][0], secondList[j][0]);
if (firstList[i][1] < secondList[j][1]) {
interval[1] = firstList[i][1];
i++;
} else if (firstList[i][1] > secondList[j][1]) {
interval[1] = secondList[j][1];
j++;
} else {
interval[1] = firstList[i][1];
i++;j++;
}
// to check valid interval [very important]
// in case i or j's start is more then i or j's end
if (interval[0] <= interval[1]) {
list.add(interval);
}
}
int[][] result = new int[list.size()][2];
for (int x=0; x< list.size(); x++) {
result[x] = list.get(x);
}
return result;
}
}