1.题目

给定两个由一些闭区间组成的列表，firstList 和 secondList ，其中 firstList[i] = [start i, end i] 而 secondList[j] = [start j, end j] 。每个区间列表都是成对不相交的，并且已经排序 。返回这两个区间列表的交集 。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。 两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

示例 1： 输入：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]]

示例 2： 输入：firstList = [[1,3],[5,9]], secondList = [ ] 输出：[ ]

示例 3： 输入：firstList = [], secondList = [[4,8],[10,12]] 输出：[ ]

示例 4： 输入：firstList = [[1,7]], secondList = [[3,10]] 输出：[[3,7]]

提示： 0 <= firstList.length, secondList.length <= 1000 firstList.length + secondList.length >= 1 0 <= start i < end i <= 109 end i < start i+1 0 <= start j < end j <= 109 end j < start j+1

2.思路

（1）双指针 ① 首先分析求两个区间交集的思路：用[start1, end1]、[start2, end2]分别表示firstList、secondList中的两个区间。经过分析可知当且仅当 end2 >= start1 && end1 >= start2 时，这两个区间才有交集，并且交集为 [Math.max(start1, start2), Math.min(end1, end2)]。 ② 知道了如何求两个区间的交集后，现在便需要遍历firstList、secondList中的区间，并求出区间列表的交集。具体做法如下： 1）定义双指针 i 和 j ，初始时它们分别指向 firstList 和 secondList 的第一个区间； 2）得到当前遍历中 firstList 的区间 [start1,end1]，secondList的区间 [start2,end2]； 3）判断[start1,end1]、[start2,end2]这两个区间是否有交集，如果有，则其交集为 [Math.max(start1, start2), Math.min(end1, end2)]，并将其保存到链表 res 中； 4）如果 end2 >= end1 ，则说明 firstList 中有可能存在其它区间与[start2,end2]有交集 ，所以 i 需要指向 firstList 的下一个区间，即 i++；否则说明 secondList 中有可能存在其它区间与[start1,end1]有交集，所以 j 需要指向 secondList 的下一个区间，即 j++。最后，当某个区间列表遍历结束时，退出循环并将 res 转换为数组即可。

3.代码实现（Java）

//思路1————双指针
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
          
   
    /*
        (1)由于不知道两个区间列表的交集个数，所以先定义链表res
        (2)将所求的结果保存到res中，然后再将其转换为数组
    */
    List<int[]> res = new LinkedList<>();
    //定义双指针
    int i = 0, j = 0;
    while (i < firstList.length && j < secondList.length) {
          
   
        //得到当前遍历中firstList的一个区间[start1,end1]，secondList的一个区间[start2,end2]
        int start1 = firstList[i][0], end1 = firstList[i][1];
        int start2 = secondList[j][0], end2 = secondList[j][1];
        //判断[start1,end1]、[start2,end2]这两个区间是否有交集
        if (end2 >= start1 && end1 >= start2) {
          
   
            //如果有交集，那么其交集为[Math.max(start1, start2), Math.min(end1, end2)]
            res.add(new int[]{
          
   Math.max(start1, start2), Math.min(end1, end2)});
        }
        if (end2 >= end1) {
          
   
        	//i指向firstList下一个区间
            i++;
        } else {
          
   
        	//j指向secondList下一个区间
            j++;
        }
    }
    return res.toArray(new int[0][0]);
}