LeetCode Solutions
986. Interval List Intersections
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
vector<vector<int>>& secondList) {
vector<vector<int>> ans;
short i = 0;
short j = 0;
while (i < firstList.size() && j < secondList.size()) {
// Lo := the start of the intersection
// Hi := the end of the intersection
const int lo = max(firstList[i][0], secondList[j][0]);
const int hi = min(firstList[i][1], secondList[j][1]);
if (lo <= hi)
ans.push_back({lo, hi});
firstList[i][1] < secondList[j][1] ? ++i : ++j;
}
return ans;
}
};
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> ans = new ArrayList<>();
short i = 0;
short j = 0;
while (i < firstList.length && j < secondList.length) {
// Lo := the start of the intersection
// Hi := the end of the intersection
final int lo = Math.max(firstList[i][0], secondList[j][0]);
final int hi = Math.min(firstList[i][1], secondList[j][1]);
if (lo <= hi)
ans.add(new int[] {lo, hi});
if (firstList[i][1] < secondList[j][1])
++i;
else
++j;
}
return ans.toArray(new int[ans.size()][]);
}
}
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
ans = []
i = 0
j = 0
while i < len(firstList) and j < len(secondList):
# Lo := the start of the intersection
# Hi := the end of the intersection
lo = max(firstList[i][0], secondList[j][0])
hi = min(firstList[i][1], secondList[j][1])
if lo <= hi:
ans.append([lo, hi])
if firstList[i][1] < secondList[j][1]:
i += 1
else:
j += 1
return ans