双指针法解决LeetCode区间列表交集问题

1. 问题概述理解区间列表的交集LeetCode 986题Interval List Intersections是一个经典的数组处理问题要求我们找出两个已排序区间列表中所有重叠的区间。这个问题在实际开发中有着广泛的应用场景比如会议室调度、时间线合并、日历冲突检测等。给定两个区间列表firstList和secondList其中每个区间都是有序且不相交的即按起始点排序且没有重叠。我们需要返回这两个列表中所有存在交集的区间组合。例如firstList [[1,3],[5,9]] secondList [[4,8]] 输出[[5,8]]2. 解题思路分析2.1 双指针法的基本原理解决这个问题最有效的方法是使用双指针技术。我们维护两个指针i和j分别指向firstList和secondList中的当前区间。通过比较这两个区间的相对位置关系我们可以确定它们是否有交集以及如何移动指针。关键点在于理解四种可能的区间关系第一个区间完全在第二个区间左侧第一个区间完全在第二个区间右侧两个区间有重叠一个区间完全包含另一个区间2.2 交集判断的数学表达两个区间[a1, a2]和[b1, b2]的交集存在当且仅当max(a1, b1) min(a2, b2)如果这个条件满足那么交集区间就是[max(a1, b1), min(a2, b2)]。这个数学表达式是我们实现算法的核心逻辑它简洁地捕捉了所有可能的重叠情况。3. C语言实现详解3.1 数据结构定义首先我们需要定义区间和结果的数据结构/** * 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 核心算法实现完整的C语言实现如下int** intervalIntersection(int** firstList, int firstListSize, int* firstListColSize, int** secondList, int secondListSize, int* secondListColSize, int* returnSize, int** returnColumnSizes) { // 分配足够大的空间存储结果 int maxPossibleSize firstListSize secondListSize; int** result (int**)malloc(sizeof(int*) * maxPossibleSize); *returnColumnSizes (int*)malloc(sizeof(int) * maxPossibleSize); int i 0, j 0; *returnSize 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 a1 b1 ? a1 : b1; int end a2 b2 ? a2 : b2; if (start end) { // 存在交集 result[*returnSize] (int*)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 复杂度分析时间复杂度O(MN)其中M和N分别是两个列表的长度。我们最多只需要遍历每个列表一次。空间复杂度O(MN)最坏情况下每个区间都有交集需要存储所有结果。4. 边界条件与测试用例4.1 常见边界情况两个列表都为空一个列表为空所有区间都没有交集所有区间都有交集一个列表完全包含在另一个列表的某个区间内区间刚好相接但没有重叠如[1,2]和[2,3]4.2 测试用例设计void testIntervalIntersection() { // 测试用例1常规情况 int firstList1[][2] {{1,3},{5,9}}; int secondList1[][2] {{4,8}}; // 预期输出[[5,8]] // 测试用例2无交集 int firstList2[][2] {{1,3},{5,7}}; int secondList2[][2] {{8,10}}; // 预期输出[] // 测试用例3完全包含 int firstList3[][2] {{1,7}}; int secondList3[][2] {{3,5}}; // 预期输出[[3,5]] // 测试用例4多个交集 int firstList4[][2] {{0,2},{5,10},{13,23},{24,25}}; int secondList4[][2] {{1,5},{8,12},{15,24},{25,26}}; // 预期输出[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] }5. 优化与扩展思考5.1 内存优化技巧在实际应用中我们可以优化内存使用预先计算可能的最大结果数量避免过度分配对于大型数据集考虑使用更高效的内存管理策略如果不需要保留结果可以边计算边处理减少内存占用5.2 实际应用场景会议室调度系统找出所有可用的会议室时间段日历应用检测两个人的空闲时间重叠基因序列比对找出DNA序列的匹配区域视频编辑找出多个视频轨道同时有内容的时间段5.3 算法变种合并多个区间列表的交集找出满足特定条件的最小/最大重叠区间统计重叠区间的总长度处理动态变化的区间列表6. 常见错误与调试技巧6.1 典型错误模式指针移动逻辑错误错误地只移动一个指针内存分配不足没有为结果分配足够空间边界条件处理不当如空列表或单个区间的情况交集判断条件错误使用错误的比较运算符6.2 调试建议打印中间结果在每次循环迭代时打印当前区间和指针位置使用可视化工具绘制区间图帮助理解逐步验证先验证简单用例再处理复杂情况单元测试为各种边界情况编写测试用例提示在LeetCode上提交时注意释放所有分配的内存否则可能导致内存泄漏错误。虽然LeetCode的测试系统可能不会检查这一点但这是良好的编程习惯。7. 性能对比与语言特性7.1 C语言实现的优势内存控制精确可以手动管理内存优化性能执行效率高没有额外的运行时开销适合嵌入式系统在资源受限环境中表现良好7.2 与其他语言的对比Python代码更简洁但运行效率较低Java有更丰富的数据结构但内存开销大C可以使用STL容器平衡了效率和便利性7.3 C语言特定注意事项指针操作要小心避免越界访问二维数组的内存布局要理解清楚返回值的内存管理要特别注意输入参数的含义要明确理解在实际面试中面试官可能会要求解释为什么选择这种实现方式以及如何进一步优化。理解算法背后的数学原理和实际应用场景能够让你在面试中脱颖而出。