LeetCode 986题解：双指针法处理区间交集问题-育师

1. 问题背景与核心挑战

LeetCode 986题"Interval List Intersections"是一个经典的区间处理问题，主要考察对有序区间的操作能力。题目给定两个已排序的区间列表，要求返回这两个列表中所有区间的交集集合。这类问题在实际开发中非常常见，比如处理日程安排冲突、资源分配重叠等场景。

我刚接触这道题时，第一反应是"这不就是双指针的变种吗？"，但实际编码时发现边界条件的处理远比想象中复杂。特别是当区间存在多种重叠情况时，稍不注意就会漏判或者重复计算。举个例子，区间A[1,5]和区间B[3,7]的交集是[3,5]，而A[1,3]和B[4,6]则没有交集。

2. 算法思路解析

2.1 双指针法的基本逻辑

解决这个问题的核心在于利用两个指针分别遍历两个区间列表。具体步骤如下：

初始化指针i和j，分别指向两个列表的起始位置
比较当前两个区间的起始和结束位置
计算可能存在的交集区间
移动结束位置较小的那个区间的指针
重复上述过程直到任一列表遍历完毕

关键点在于如何正确计算两个区间的交集。数学上，两个区间[a1, a2]和[b1, b2]的交集存在当且仅当a1 <= b2且b1 <= a2。如果存在交集，则交集区间为[max(a1,b1), min(a2,b2)]。

2.2 C语言实现细节

在C语言实现时，我们需要特别注意内存管理和数组操作。以下是核心代码片段：

int** intervalIntersection(int** firstList, int firstListSize, int* firstListColSize, int** secondList, int secondListSize, int* secondListColSize, int* returnSize, int** returnColumnSizes){ int **result = malloc(sizeof(int*) * (firstListSize + secondListSize)); *returnColumnSizes = malloc(sizeof(int) * (firstListSize + secondListSize)); *returnSize = 0; int i = 0, j = 0; while(i < firstListSize && j < secondListSize){ int a1 = firstList[i][0], a2 = firstList[i][1]; int b1 = secondList[j][0], b2 = secondList[j][1]; // 检查是否有交集 if(a2 >= b1 && b2 >= a1){ // 计算交集 int start = a1 > b1 ? a1 : b1; int end = a2 < b2 ? a2 : b2; // 存储结果 result[*returnSize] = malloc(sizeof(int)*2); result[*returnSize][0] = start; result[*returnSize][1] = end; (*returnColumnSizes)[*returnSize] = 2; (*returnSize)++; } // 移动指针 if(a2 < b2) i++; else j++; } return result; }

3. 边界条件与特殊处理

3.1 空输入处理

在实际编码中，我们必须考虑以下几种边界情况：

其中一个列表为空
两个列表都为空
列表中存在空区间（如[3,3]表示单个点）

在C语言实现中，对空输入的处理尤为重要。例如，当firstListSize为0时，我们应该立即返回空数组，而不是继续执行后续逻辑。

3.2 内存管理要点

C语言需要手动管理内存，这里有几个关键注意事项：

预先分配足够大的结果数组（通常是两个列表大小之和）
为每个交集区间单独分配内存
记得为returnColumnSizes分配内存
调用者需要负责释放这些内存

一个常见的错误是忘记为returnColumnSizes分配内存，这会导致运行时错误。另一个陷阱是结果数组预分配过大造成内存浪费，或者过小导致越界。

4. 复杂度分析与优化

4.1 时间复杂度

该算法的时间复杂度是O(m+n)，其中m和n分别是两个列表的长度。这是因为每个指针最多移动m+n次，每次操作都是常数时间。

4.2 空间复杂度

空间复杂度也是O(m+n)，最坏情况下需要存储所有可能的交集区间。在实际应用中，如果交集很少，可以考虑动态调整内存分配策略，但这会增加代码复杂度。

5. 实际应用场景

这类区间交集问题在实际开发中有广泛应用：

会议系统：查找多个参与者的共同空闲时间
资源调度：确定设备可用的重叠时间段
基因组学：查找DNA序列的重叠区域
日志分析：找出多个服务同时出现异常的时段

理解这个算法不仅能帮助通过面试，更能为解决实际问题提供思路。例如，在处理用户行为日志时，我经常需要找出多个事件序列的共同发生时段，这时类似的区间处理技巧就派上用场了。

6. 常见错误与调试技巧

6.1 典型错误案例

在实现这个算法时，我遇到过几个典型的bug：

指针移动逻辑错误：错误地总是移动第一个指针
交集判断条件错误：遗漏了a2 >= b1的条件
内存分配不足：没有预分配足够的结果空间
忘记设置returnColumnSizes的值

6.2 调试建议

对于这类问题，我建议使用以下测试用例进行验证：

常规情况：
- 输入：[[1,3],[5,9]] 和 [[2,5],[7,10]]
- 预期输出：[[2,3],[5,5],[7,9]]
无交集情况：
- 输入：[[1,3],[5,7]] 和 [[8,10]]
- 预期输出：[]
完全包含情况：
- 输入：[[1,7]] 和 [[3,5]]
- 预期输出：[[3,5]]
单点区间：
- 输入：[[1,1],[3,3]] 和 [[1,3]]
- 预期输出：[[1,1],[3,3]]

在LeetCode上提交前，务必在本地用这些测试用例验证你的代码。特别是对于C语言实现，内存错误往往不会立即导致程序崩溃，但会在评测时产生不可预测的结果。

7. 扩展思考

7.1 变种问题

掌握了基础解法后，可以尝试解决一些变种问题：

处理未排序的区间列表（需要先排序）
合并多个区间列表的交集
计算交集的持续总时间
找出满足特定条件的最长交集

7.2 性能优化

对于特别大的区间列表，可以考虑以下优化：

提前终止：当剩余区间不可能再有交集时提前结束
并行处理：将列表分段后并行计算
区间压缩：预处理时合并相邻或重叠区间

不过在实际面试中，通常只需要实现基础解法即可，除非特别说明有性能要求。

8. 编码风格建议

在C语言实现这类算法题时，良好的编码风格很重要：

为指针操作添加注释
合理命名变量（如用i,j作指针，a1/a2表示区间端点）
保持函数单一职责（不要在一个函数里做太多事情）
添加必要的空行分隔逻辑块
为复杂条件添加解释性注释

例如，交集判断条件可以这样注释：

// Check if intervals overlap // a: [a1, a2], b: [b1, b2] // They overlap if a2 >= b1 && b2 >= a1 if(a2 >= b1 && b2 >= a1){ // ... }

这样的代码不仅更容易调试，也便于面试官理解你的思路。

9. 与其他语言的对比

虽然题目要求用C实现，但了解其他语言的解法也有助于加深理解：

Python可以利用列表推导简化代码：

def intervalIntersection(A, B): i = j = 0 res = [] while i < len(A) and j < len(B): a_start, a_end = A[i] b_start, b_end = B[j] # Calculate overlap start = max(a_start, b_start) end = min(a_end, b_end) if start <= end: res.append([start, end]) # Move pointer if a_end < b_end: i += 1 else: j += 1 return res

Java则需要处理更多的样板代码，但思路相同。相比之下，C语言版本虽然更冗长，但执行效率通常更高，也更能体现对内存管理的掌握程度。