区间交集算法 题目描述：给定两个由闭区间组成的列表，每个区间列表都是成对不相交的，并且已经排序。请返回这两个区间列表的交集。 示例： 输入：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]的交集是[ max(a,c), min(b,d) ]，当且仅当max(a,c) ≤ min(b,d) 双指针解法思路： 使用两个指针i和j分别遍历两个列表 比较当前两个区间firstList[ i]和secondList[ j ] 计算它们的交集（如果存在） 移动结束位置较早的那个区间的指针 详细步骤： 步骤1：初始化i = 0, j = 0，结果列表result = [ ] 步骤2：当i < firstList.length且j < secondList.length时循环： a. 设A = firstList[ i], B = secondList[ j ] b. 计算两个区间的重叠部分： start = max(A[ 0], B[ 0 ]) end = min(A[ 1], B[ 1 ]) d. 如果start ≤ end，说明有交集，将[ start, end ]加入结果 e. 移动指针：比较A[ 1]和B[ 1 ] 如果A[ 1] < B[ 1 ]，i++（A区间结束更早） 否则j++（B区间结束更早或同时结束） 示例推演： 初始：i=0, j=0 A=[ 0,2], B=[ 1,5] → 交集[ 1,2] → i++（因为2 <5） i=1, j=0 A=[ 5,10], B=[ 1,5] → 交集[ 5,5 ] → j++（因为5=5） i=1, j=1 A=[ 5,10], B=[ 8,12] → 交集[ 8,10] → i++（因为10 <12） i=2, j=1 A=[ 13,23], B=[ 8,12] → 无交集 → j++（因为12 <13） i=2, j=2 A=[ 13,23], B=[ 15,24] → 交集[ 15,23] → i++（因为23 <24） i=3, j=2 A=[ 24,25], B=[ 15,24] → 交集[ 24,24 ] → j++（因为24=24） i=3, j=3 A=[ 24,25], B=[ 25,26] → 交集[ 25,25 ] → i++,j++ 算法复杂度： 时间复杂度：O(m+n)，其中m和n是两个列表的长度 空间复杂度：O(1)（不考虑输出结果的空间）