区间交集问题

本文是区间系列问题的第三篇，前两篇分别讲了区间的最大不相交子集和重叠区间的合并，今天再写一个算法，可以快速找出两组区间的交集。

先看下题目，LeetCode 第 986 题就是这个问题：

title

题目很好理解，就是让你找交集，注意区间都是闭区间。

思路

解决区间问题的思路一般是先排序，以便操作，不过题目说已经排好序了，那么可以用两个索引指针在 A 和 B 中游走，把交集找出来，代码大概是这样的：

  1. # A, B 形如 [[0,2],[5,10]...]
  2. def intervalIntersection(A, B):
  3.     i, j = 0, 0
  4.     res = []
  5.     while i < len(A) and j < len(B):
  6.         # ...
  7.         j += 1
  8.         i += 1
  9.     return res

不难，我们先老老实实分析一下各种情况。

首先，对于两个区间，我们用 [a1,a2] 和 [b1,b2] 表示在 A 和 B 中的两个区间，那么什么情况下这两个区间没有交集呢：

区间交集问题 - 图2

只有这两种情况，写成代码的条件判断就是这样：

  1. if b2 < a1 or a2 < b1:
  2.     [a1,a2] 和 [b1,b2] 无交集

那么，什么情况下，两个区间存在交集呢？根据命题的否定，上面逻辑的否命题就是存在交集的条件：

  1. # 不等号取反，or 也要变成 and
  2. if b2 >= a1 and a2 >= b1:
  3.     [a1,a2] 和 [b1,b2] 存在交集

接下来，两个区间存在交集的情况有哪些呢？穷举出来：

区间交集问题 - 图3

这很简单吧，就这四种情况而已。那么接下来思考，这几种情况下，交集是否有什么共同点呢？

区间交集问题 - 图4

我们惊奇地发现，交集区间是有规律的！如果交集区间是 [c1,c2]，那么 c1=max(a1,b1)，c2=min(a2,b2)！这一点就是寻找交集的核心，我们把代码更进一步：

  1. while i < len(A) and j < len(B):
  2.     a1, a2 = A[i][0], A[i][1]
  3.     b1, b2 = B[j][0], B[j][1]
  4.     if b2 >= a1 and a2 >= b1:
  5.         res.append([max(a1, b1), min(a2, b2)])
  6.     # ...

最后一步，我们的指针 i 和 j 肯定要前进（递增）的，什么时候应该前进呢？

区间交集问题 - 图5

结合动画示例就很好理解了，是否前进，只取决于 a2 和 b2 的大小关系：

  1. while i < len(A) and j < len(B):
  2.     # ...
  3.     if b2 < a2:
  4.         j += 1
  5.     else:
  6.         i += 1

代码

  1. # A, B 形如 [[0,2],[5,10]...]
  2. def intervalIntersection(A, B):
  3.     i, j = 0, 0 # 双指针
  4.     res = []
  5.     while i < len(A) and j < len(B):
  6.         a1, a2 = A[i][0], A[i][1]
  7.         b1, b2 = B[j][0], B[j][1]
  8.         # 两个区间存在交集
  9.         if b2 >= a1 and a2 >= b1:
  10.             # 计算出交集，加入 res
  11.             res.append([max(a1, b1), min(a2, b2)])
  12.         # 指针前进
  13.         if b2 < a2: j += 1
  14.         else:       i += 1
  15.     return res

总结一下，区间类问题看起来都比较复杂，情况很多难以处理，但实际上通过观察各种不同情况之间的共性可以发现规律，用简洁的代码就能处理。

另外，区间问题没啥特别厉害的奇技淫巧，其操作也朴实无华，但其应用却十分广泛，接之前的几篇文章：

kingkong1111提供 Java 代码:

  1. public int[][] intervalIntersection(int[][] A, int[][] B) {
  2.         List<int[]> res = new ArrayList<>();
  3.         if (A == null || B == null) {
  4.             return res.toArray(new int[0][]);
  5.         }
  6.         // 定义两个指针遍历两个数组
  7.         int i =0;
  8.         int j =0;
  9.         while (i < A.length && j < B.length) {
  10.             int a1 = A[i][0];
  11.             int a2 = A[i][1];
  12.             int b1 = B[j][0];
  13.             int b2 = B[j][1];
  14.             //1 说明有重合
  15.             if (a1 <= b2 && a2 >= b1) {
  16.                 //2 重合区间：前面的最大值 到 后面的最小值
  17.                 int start = Math.max(a1, b1);
  18.                 int end = Math.min(a2, b2);
  19.                 res.add(new int[]{start, end});
  20.             }
  21.             //3 哪个区间大，哪个不动，另一个指针动，看是否能扩大重合区间
  22.             if (a2 > b2) {
  23.                 j++;
  24.             } else {
  25.                 i++;
  26.             }
  27.         }
  28.         return res.toArray(new int[0][]);
  29.     }