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

闪念标签：LC

题目链接：https://leetcode.cn/problems/interval-list-intersections/