求两个有序无相交区间列表交集的精简高效代码实现方法

解法逻辑 #

给定的两个区间列表均满足内部无相交、升序排列的特性，使用双指针法遍历即可达到最优的O(m+n)时间复杂度，无需嵌套循环遍历所有区间组合。

精简代码实现（Python） #

def interval_intersection(first: list[list[int]], second: list[list[int]]) -> list[list[int]]:
    i = j = 0
    res = []
    while i < len(first) and j < len(second):
        a_s, a_e, b_s, b_e = *first[i], *second[j]
        if a_e >= b_s and b_e >= a_s:
            res.append([max(a_s, b_s), min(a_e, b_e)])
        i, j = i + (a_e < b_e), j + (b_e <= a_e)
    return res

验证效果 #

• 示例1输入：
  firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]
  输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]，完全匹配预期
• 示例2输入：
  firstList = [[1,3],[5,9]]
secondList = []
  输出：[]，完全匹配预期

优化说明 #

1. 利用Python的解包语法简化区间端点的取值逻辑，减少冗余代码
2. 用布尔值隐式转换为0/1实现指针步进，省略了多分支判断的冗余代码
3. 仅需一次遍历即可完成计算，是该场景下理论最优的时间复杂度，空间占用仅需存储结果的额外开销

内容的提问来源于stack exchange，提问作者user4516038