## 1. 问题背景与核心需求 这道LeetCode 986题要求我们计算两个已排序区间列表的交集。在实际开发中区间交集计算是日程安排系统、资源调度、时间线合并等场景的常见需求。比如合并两个团队的会议时间表或者计算两个服务同时可用的时间段。 给定两个区间列表firstList和secondList其中每个区间都是排好序且不相交的按起始点升序排列。我们需要返回这两个列表中所有区间的交集构成的列表。 ## 2. 算法思路解析 ### 2.1 双指针法的选择理由 这道题最自然的解法是使用双指针法原因在于 1. 两个列表都已排序这是双指针法的前置条件 2. 我们需要同时遍历两个列表比较当前区间的关系 3. 时间复杂度可以优化到O(mn)空间复杂度O(1)不考虑结果存储 ### 2.2 区间交集的数学表达 两个区间[a1, a2]和[b1, b2]的交集存在当且仅当 max(a1, b1) min(a2, b2) 此时交集区间为 [max(a1, b1), min(a2, b2)] ## 3. C语言实现详解 ### 3.1 数据结构定义 c /** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. */ int** intervalIntersection(int** firstList, int firstListSize, int* firstListColSize, int** secondList, int secondListSize, int* secondListColSize, int* returnSize, int** returnColumnSizes) { // 实现代码 }3.2 核心算法实现int** result malloc(sizeof(int*) * (firstListSize secondListSize)); *returnColumnSizes malloc(sizeof(int) * (firstListSize secondListSize)); int count 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]; // 计算交集 int start max(a1, b1); int end min(a2, b2); if (start end) { result[count] malloc(sizeof(int) * 2); result[count][0] start; result[count][1] end; (*returnColumnSizes)[count] 2; count; } // 移动指针 if (a2 b2) { i; } else { j; } } *returnSize count; return result;3.3 关键点解析内存分配预先分配足够大的结果数组避免频繁realloc指针移动逻辑总是结束较早的区间指针向前移动边界处理严格处理区间端点相等的情况4. 复杂度分析与优化4.1 时间复杂度最佳情况O(min(m,n))最坏情况O(mn)平均情况O(mn)4.2 空间复杂度结果存储O(k)k为交集数量算法本身O(1)额外空间4.3 可能的优化方向原地修改输入数组如果允许使用更紧凑的内存布局如连续存储并行化处理对于超大列表5. 测试用例设计5.1 常规测试用例// 用例1简单交集 firstList [[1,3],[5,9]] secondList [[2,5],[7,10]] // 预期结果[[2,3],[5,5],[7,9]] // 用例2无交集 firstList [[1,2],[5,6]] secondList [[3,4],[7,8]] // 预期结果[]5.2 边界测试用例// 用例3端点重合 firstList [[1,3],[5,7]] secondList [[3,5],[7,9]] // 预期结果[[3,3],[5,5],[7,7]] // 用例4一个列表为空 firstList [] secondList [[1,2],[3,4]] // 预期结果[]6. 常见错误与调试技巧6.1 典型错误模式指针移动错误错误地同时移动两个指针内存分配不足没有预分配足够的结果空间端点处理不当忽略等于的情况如[5,5]6.2 调试建议打印双指针位置和当前比较的区间可视化区间关系画数轴图单元测试覆盖所有边界情况7. 实际应用场景扩展会议时间安排找出所有参与者都有空的时间段资源预约系统计算资源可用的公共时间段基因序列比对找出DNA序列匹配的区间提示在实际工程中可能还需要处理区间列表的动态更新这时可以考虑使用区间树等更高级的数据结构。8. 算法变种与延伸思考多列表交集扩展到N个区间列表的交集计算区间合并先合并每个列表内部的重叠区间带权区间每个区间带有权重值求最大权重交集我在实际编码中发现处理区间问题时画图特别有帮助。建议先用纸笔画出区间的位置关系再转化为代码逻辑这样可以避免很多边界条件错误。另外在C语言中要特别注意内存管理确保没有泄漏。