JZX轻语：简
LeetCode 986 - 区间列表的交集
发表于2024年05月31日
双指针典型题目。使用两个指针i和j分别指向A和B的区间，然后根据两个区间的交集(两个区间的最大左端点和最小右端点)来更新答案。指针的移动规则是：如果A区间的右端点小于等于B区间的右端点(A区间位于B左侧，说明A的下一个区间可能和B当前区间还是会有交集)，那么A区间的指针i向右移动；否则B区间的指针j向右移动。
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
i = j = 0
ans = []
while i < len(firstList) and j < len(secondList):
min_r = min(firstList[i][1], secondList[j][1])
max_l = max(firstList[i][0], secondList[j][0])
if max_l <= min_r:
ans.append([max_l, min_r])
if firstList[i][1] <= secondList[j][1]:
i += 1
else:
j += 1
return ans