区间列表的交集：双指针处理区间问题的通用模式

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 16 分钟 | 难度：⭐⭐⭐

---

开篇故事

区间问题是工程中非常常见的一类问题，比如日历系统中的会议冲突检测、网络协议中的地址段匹配、数据库中的时间范围查询。

我在做一个排班系统的时候，需要找出两组员工时间段的重叠部分。最开始我用了嵌套循环，O(m*n) 的复杂度。后来意识到两组区间都是按时间排序的，完全可以用双指针一次扫描解决。

LeetCode 986 就是这道经典的区间交集题目，它把双指针应用到了区间场景，而不是普通的数组元素比较。理解了这道题的模式，你就掌握了处理两个有序区间列表的通用思路。

---

一、题目解析

题目（LeetCode 986）： 给定两个按起始点排序的区间列表 firstList 和 secondList，返回这两个区间列表的交集。

示例：

• 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]]

关键观察：

• 两个区间 [a, b] 和 [c, d] 有交集，当且仅当 a <= d 且 c <= b（即 max(a,c) <= min(b,d)）。
• 交集是 [max(a,c), min(b,d)]。
• 处理完当前一对区间后，结束早的那个（右端点更小的）对应的指针前进。

---

二、解法一：暴力 O(m*n)

public class Solution1 {
    public int[][] intervalIntersection(int[][] first, int[][] second) {
        List<int[]> result = new ArrayList<>();
        for (int[] a : first) {
            for (int[] b : second) {
                int lo = Math.max(a[0], b[0]);
                int hi = Math.min(a[1], b[1]);
                if (lo <= hi) {
                    result.add(new int[]{lo, hi});
                }
            }
        }
        return result.toArray(new int[0][]);
    }
}

复杂度分析

• 时间复杂度：O(m*n)。
• 空间复杂度：O(k)，k 为交集数量。

---

三、解法二：排序合并后扫描（适用于未排序输入）

如果输入未排序，先排序再用解法三，总体 O((m+n)log(m+n))。这里不展开，直接利用题目"已排序"的条件。

---

四、解法三最优：双指针一次扫描 O(m+n)

思路分析

i 指向 firstList，j 指向 secondList。每步：

1. 取当前两个区间，计算交集（如果有的话）。
2. 将右端点更小的那个区间的指针前进（因为该区间不可能与另一个列表后续的区间有交集——另一个列表的后续区间起点更大）。

为什么右端点更小的那个指针前进？

设当前区间是 firstList[i] = [a, b] 和 secondList[j] = [c, d]，且 b < d。 那么 firstList[i] 与 secondList[j+1], secondList[j+2], ... 的交集如何？ secondList[j+1] 的起点 >= d > b，所以 secondList[j+1] 的起点已经超过了 firstList[i] 的终点 b，无交集。 因此 firstList[i] 与 secondList 后续所有区间都无交集，可以放心 i++。

Mermaid 图

完整代码

public class Solution3 {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;

        while (i < firstList.length && j < secondList.length) {
            // 计算当前两区间的交集
            int lo = Math.max(firstList[i][0], secondList[j][0]);
            int hi = Math.min(firstList[i][1], secondList[j][1]);

            // 如果有交集，记录下来
            if (lo <= hi) {
                result.add(new int[]{lo, hi});
            }

            // 右端点更小的指针前进
            if (firstList[i][1] < secondList[j][1]) {
                i++;  // firstList 当前区间结束更早
            } else {
                j++;  // secondList 当前区间结束更早（含相等情况）
            }
        }

        return result.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();

        int[][] first = {{0,2},{5,10},{13,23},{24,25}};
        int[][] second = {{1,5},{8,12},{15,24},{25,26}};
        int[][] res = sol.intervalIntersection(first, second);
        for (int[] r : res) {
            System.out.print(Arrays.toString(r) + " ");
        }
        System.out.println();
        // [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

        // 无交集
        int[][] f2 = {{0,1}};
        int[][] s2 = {{2,3}};
        System.out.println(sol.intervalIntersection(f2, s2).length); // 0

        // 完全重叠
        int[][] f3 = {{0,5}};
        int[][] s3 = {{0,5}};
        res = sol.intervalIntersection(f3, s3);
        for (int[] r : res) System.out.print(Arrays.toString(r));
        System.out.println(); // [0,5]
    }
}

复杂度分析

• 时间复杂度：O(m+n)。i 和 j 分别最多移动 m 和 n 次。
• 空间复杂度：O(k)，k 为交集数量（不计结果空间则 O(1)）。

---

五、举一反三

题号	题目	关联点
56	合并区间	单列表的区间合并，排序后扫描
57	插入区间	在已排序列表中插入一个新区间
252	会议室	判断区间是否有重叠
253	会议室 II	最少需要多少会议室（贪心+堆）
435	无重叠区间	最少移除多少区间使无重叠

区间问题核心操作模板：

// 判断两区间是否有交集
boolean hasIntersection(int[] a, int[] b) {
    return Math.max(a[0], b[0]) <= Math.min(a[1], b[1]);
}

// 计算两区间的交集（假设有交集）
int[] intersect(int[] a, int[] b) {
    return new int[]{Math.max(a[0], b[0]), Math.min(a[1], b[1])};
}

// 合并两个相交的区间
int[] merge(int[] a, int[] b) {
    return new int[]{Math.min(a[0], b[0]), Math.max(a[1], b[1])};
}

---

六、踩坑实录

坑一：前进哪个指针的逻辑错误

应该前进右端点更小的那个指针，但有人写成了"前进左端点更小的那个指针"，这会导致漏掉一些有效交集。左端点决定的是区间从哪里开始，而右端点决定的是区间何时结束——结束更早的那个不可能跟后续区间有交集。

坑二：等于号的归属

当 firstList[i][1] == secondList[j][1] 时，两个区间同时结束，需要 i 和 j 都前进。但在 if-else 结构中，等于号归属于任意一侧都行——下一次循环会处理另一个。但不能两个都不前进（死循环）也不能只前进一个然后立即退出（可能漏掉最后的交集）。代码里 else { j++; } 处理了等号情况，i 留给下一轮，没有问题。

坑三：空列表输入

当 firstList 或 secondList 为空时，循环条件 i < firstList.length && j < secondList.length 直接为假，返回空列表，正确处理。

坑四：结果中出现单点区间（lo == hi）

单点区间 [x, x] 是合法的，不应该过滤掉。题目也包含了这种情况（如示例中的 [5,5]）。

---

七、总结

区间双指针模式的核心决策只有一条：每步处理当前两个区间（计算交集），然后右端点更早结束的那个区间不可能与另一侧的后续区间有交集，前进对应指针。

这个模式在区间问题里非常通用，合并区间、找区间交集、统计重叠次数等问题都能用它来处理。在工程代码里，处理日历、时间段、地址段等结构化数据时，这个模式的应用非常广泛。