区间交集算法（多区间交集） 题目描述 给定多个区间列表（每个列表内的区间已经按左端点排序且内部不相交），找出所有区间列表中都存在的公共区间。例如： 列表1: [ [ 1, 3], [ 5, 9] ] 列表2: [ [ 2, 4], [ 6, 8] ] 列表3: [ [ 0, 7] ] 需要返回所有列表的公共区间：[ [ 2, 3], [ 6, 7] ]。 解题过程 步骤1: 理解问题核心 公共区间需满足两个条件： 在每个列表中至少存在一个区间包含该公共区间。 公共区间本身是连续的（即仍是区间形式）。 关键思路： 逐层比较 ，每次处理两个列表的公共区间，再将结果与下一个列表比较。 步骤2: 两个区间列表的交集算法 假设有两个区间列表 A 和 B ，均已排序。 使用双指针 i （指向列表A的当前区间）和 j （指向列表B的当前区间）。 比较当前区间 A[i] 和 B[j] ： 若两区间有重叠（即 A[i] 的右端点 ≥ B[j] 的左端点，且 A[i] 的左端点 ≤ B[j] 的右端点），则重叠部分为： [max(A[i][0], B[j][0]), min(A[i][1], B[j][1])] 。 将重叠区间加入结果。 移动指针： 丢弃右端点较小的区间 （因为该区间不可能再与另一个列表的后续区间重叠）。 重复直到任一列表遍历完。 示例 ： A: [ [ 1, 3], [ 5, 9] ] B: [ [ 2, 4], [ 6, 8] ] 比较 [ 1,3] 和 [ 2,4] → 重叠 [ 2,3]；移动 i（因3 <4）。 比较 [ 5,9] 和 [ 2,4] → 无重叠；移动 j（因4 <5）。 比较 [ 5,9] 和 [ 6,8] → 重叠 [ 6,8]；移动 j（因8 <9）。 结果：[ [ 2,3], [ 6,8] ]。 步骤3: 扩展到多个列表 初始公共区间列表设为第一个列表。 依次与第二个、第三个...列表计算交集： 每次调用步骤2的算法，得到当前公共区间与下一个列表的交集。 最终结果即为所有列表的公共区间。 示例 （接步骤2示例）： 当前公共区间: [ [ 2,3], [ 6,8] ] 列表3: [ [ 0,7] ] 比较 [ 2,3] 和 [ 0,7] → 重叠 [ 2,3]；移动 i（因3 <7）。 比较 [ 6,8] 和 [ 0,7] → 重叠 [ 6,7]；移动 j（因7 <8）。 结果：[ [ 2,3], [ 6,7] ]。 步骤4: 算法复杂度 设每个列表平均有 m 个区间，共 k 个列表。 每轮交集操作时间复杂度为 O(m + m') （ m' 为当前公共区间数）。 总复杂度： O(k * m) ，因为公共区间数不会超过 m 。 步骤5: 边界情况处理 若某列表为空，直接返回空结果。 区间比较时注意开闭区间（本题默认闭区间）。 重叠区间长度为0（如 [ 2,2 ]）是否保留需根据题意（通常保留）。