如何求两个区间列表的交集？（LeetCode 986）

简化版

给两个各自有序且内部不重叠的区间列表 A 和 B，求它们的交集（所有同时被 A、B 覆盖的区间段）。用双指针：i、j 分别指向 A、B 当前区间，两区间的交集是 [max(A[i].start, B[j].start), min(A[i].end, B[j].end)]，若这个区间左端 <= 右端则是有效交集，加入结果；然后谁的右端点小就移动谁的指针（右端小的那个区间已经用尽，可以跳过）。

详细版

int[][] intervalIntersection(int[][] A, int[][] B) {
    List<int[]> res = new ArrayList<>();
    int i = 0, j = 0;
    while (i < A.length && j < B.length) {
        int lo = Math.max(A[i][0], B[j][0]);   // 交集左端 = 两左端较大者
        int hi = Math.min(A[i][1], B[j][1]);   // 交集右端 = 两右端较小者
        if (lo <= hi) {                         // 有交集
            res.add(new int[]{lo, hi});
        }
        // 右端点小的区间先"结束"，移动它的指针
        if (A[i][1] < B[j][1]) i++;
        else j++;
    }
    return res.toArray(new int[res.size()][]);
}

交集公式：两区间交集 = [max(左端), min(右端)]，当 左 <= 右 才有效。
移动策略：比较两区间的右端点，右端小的那个用完了，移它的指针；右端大的可能还能和对方下一个区间相交，留着。
复杂度：O(m + n)，双指针各扫一遍。

完整版教学

一、题意：两个有序区间列表的「归并式求交」

两个列表 A、B 各自有序、内部不重叠。要找出所有「A 和 B 都覆盖到」的时间段。因为两边都有序，可以像归并两个有序数组那样用双指针同步推进，O(m+n) 完成——不需要嵌套两层循环。

二、两区间的交集怎么算

任取 A 的一个区间 [a1, a2] 和 B 的一个区间 [b1, b2]，它们的交集是：

[ max(a1, b1),  min(a2, b2) ]

即左端取两者较大（交集从更晚开始的那个起点算起）、右端取两者较小（到更早结束的那个终点为止）。若算出来 左端 <= 右端，说明确实有重叠部分，是个有效交集；若 左端 > 右端，说明这两个区间根本不相交（一个完全在另一个左边），无交集。

三、指针移动的关键：移「右端点小」的那个

算完当前 A[i] 和 B[j] 的交集后，要决定移哪个指针。规则：比较两区间的右端点，谁的右端点小就移谁。

道理：右端点小的那个区间，到此已经「彻底用尽」——它右边界之后的部分不存在了，不可能再和对方后续区间相交。而右端点大的那个区间，还延伸得更远，可能和对方的下一个区间继续相交，所以留着它、移动小的。

举例：A[i]=[1,7]、B[j]=[3,5]。交集 [3,5]。B[j] 右端 5 < A[i] 右端 7，所以移 j——因为 [3,5] 已经结束，而 [1,7] 还能和 B 的下一个区间（比如 [6,8]）相交出 [6,7]。

四、为什么不会漏解、不会重复

不漏：因为每次都保留「右端更大」的区间，它会依次和对方能相交的所有区间求交，不会跳过任何一对可能相交的。
不重复：交集区间是按左端从小到大依次产生的（双指针单调前进），每段交集只在对应的一对 (A[i], B[j]) 处生成一次。
有序性保证：正因 A、B 内部有序不重叠，才能断言「右端小的区间用完后无需回头」，这是双指针成立的根基。

五、边界与陷阱

相接算不算交集：[1,2] 和 [2,3] 交于单点 [2,2]。LeetCode 986 认为这算有效交集（lo <= hi 取 <=，2 <= 2 成立，输出 [2,2]）。若题目要求「交集必须有正长度」，改成 lo < hi。
移动条件的等号：A[i][1] < B[j][1] 时移 i。当两者右端相等时，移哪个都行（代码走 else 移 j），因为两个都用尽了；不会出错。
空列表：任一为空，while 直接不进，返回空结果。

六、排序键、扫描不变量与边界语义

本题扫描成立的结构是：两当前区间交集为 [max(l1,l2),min(r1,r2)]，若非空则记录；随后移动右端较小者。

右端较小的区间不可能再与对方后续更靠右区间相交，因此可安全丢弃

数字推演：A=[0,2],[5,10]，B=[1,5],[8,12] 依次得到 [1,2],[5,5],[8,10]（闭区间）。

扫描过程中要始终说明已经处理部分被压缩成什么状态，以及为什么更早区间不必再看。实现边界是：列表必须各自有序且内部不重叠；左右端相等是否算交集取决于语义。

记忆钩子：区间题先写端点语义，再选排序键；小于还是小于等于不是代码风格，而是问题定义。

七、方法对比与专项测试

问题结构	常用工具
静态合并或覆盖	排序后线性扫描
选择最多不重叠	按右端排序的贪心
最大同时重叠	扫描线或最小堆
两个有序列表求交	双指针
动态预约	有序树或线段树

测试必须覆盖空输入、单区间、完全分离、完全嵌套、链式重叠、相同起点或终点，以及端点恰好相接。若排序比较器用端点相减，还要加入整数极值检查溢出。

正确性复核要落到本题的排除逻辑：两当前区间交集为 [max(l1,l2),min(r1,r2)]，若非空则记录；随后移动右端较小者。这保证扫描指针越过某段后，它不可能再与未来候选形成更优或遗漏的答案。

已处理区间 ──压缩为边界/堆/结果尾段──> 当前区间
       │                                  │
       └─ 已由排序与端点关系证明无需回看 ─┘
当前决策完成后，指针只向右移动

在数字样例“A=[0,2],[5,10]，B=[1,5],[8,12] 依次得到 [1,2],[5,5],[8,10]（闭区间）”上，应逐轮写出被保留的边界和被丢弃的区间。若某一步无法解释为什么丢弃安全，就说明排序键、端点不等号或状态定义仍有问题。

工程上还要单独确认：列表必须各自有序且内部不重叠；左右端相等是否算交集取决于语义。这些条件变化会直接改变重叠判定或所需数据结构，不能只修改一个比较符后沿用原证明。

八、常见误区与追问

误区：相交后两个指针都移动。 右端较大的区间可能继续与下一段相交。
误区：移动左端较小者。 应移动更早结束者。
误区：max(left)≤min(right) 永远适用。 该不等号对应闭区间。
追问：为何不会漏交集？ 被移除区间结束后无法碰到对方后续区间。
追问：列表内部有重叠怎么办？ 应先归并或改算法，标准双指针前提失效。
追问：复杂度是多少？ O(m+n)，额外 O(1) 不计结果。

九、加强记忆

区间列表的交集 = 双指针归并求交（两列表各自有序不重叠，故 O(m+n)）。当前两区间交集 = [max(两左端), min(两右端)]，左 <= 右 才有效加入。算完后移动「右端点较小」的那个指针（它已用尽，右端大的还能和对方后续相交）。有序性保证不漏不重、无需回头。相接单点算不算交集决定 <= 还是 <（986 算，用 <=）。核心两句：交集取「左大右小」，移指针移「右端小」。

简化版

详细版