给定两个由一些闭区间组成的列表，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

思路

维护双指针i，j，各自指向两个区间列表，对应[starti,endi]和[startj,endj]。

其实如果两个区间[starti,endi]和[startj,endj]存在交集，则必然遵循这样的规律：

    1. endj必然大于等于starti，同时，endi必然大于等于startj。
    1. 交集的开闭区间必然为[max(starti,startj),min(endi,endj)]。

相交区间

同时，对于区间的末尾，需要做判断：

  • 如果endi在endj之后，说明区间i向后延伸更长的范围，可能会和下一个区间j有交集，此时需要判断下一个j区间。

  • 如果endj在endi之后，说明区间j向后延伸更长的范围，可能会和下一个区间i有交集，此时需要判断下一个i区间。

思路递推

以实例一中的firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]为例：

  • 初始化，i = 0，j = 0。
  • [starti,endi]对应[0,2],[startj,endj]对应[1,5]，发现endj大于等于starti且endi大于等于startj，得到相交区间[max(starti,startj),min(endi,endj)] = [1,2]，加入结果集。
  • 此时endj大于endi，说明区间j向后延伸更长的范围，可能会和下一个区间i有交集，此时需要判断下一个i区间，因此i++向后递进。
  • i = 1，j = 0。
  • [starti,endi]对应[5,10],[startj,endj]对应[1,5]，发现endj大于等于starti且endi大于等于startj，得到相交区间[max(starti,startj),min(endi,endj)] = [5,5]，加入结果集。
  • 此时endi大于endj，说明区间i向后延伸更长的范围，可能会和下一个区间j有交集，此时需要判断下一个j区间，因此j++向后递进。
  • i = 1，j = 1。
  • [starti,endi]对应[5,10],[startj,endj]对应[8,12]，发现endj大于等于starti且endi大于等于startj，得到相交区间[max(starti,startj),min(endi,endj)] = [8,10]，加入结果集。
  • 此时endj大于endi，说明区间j向后延伸更长的范围，可能会和下一个区间i有交集，此时需要判断下一个i区间，因此i++向后递进。
  • i = 2，j = 1。
  • [starti,endi]对应[13,23],[startj,endj]对应[8,12]，发现不满足endj大于等于starti且endi大于等于startj，无法得到相交区间。
  • 此时endi大于endj，说明区间i向后延伸更长的范围，可能会和下一个区间j有交集，此时需要判断下一个j区间，因此j++向后递进。
  • i = 2，j = 2。
  • [starti,endi]对应[13,23],[startj,endj]对应[15,24]，发现endj大于等于starti且endi大于等于startj，得到相交区间[max(starti,startj),min(endi,endj)] = [15,23]，加入结果集。
  • 此时endj大于endi，说明区间j向后延伸更长的范围，可能会和下一个区间i有交集，此时需要判断下一个i区间，因此i++向后递进。
  • i = 3，j = 2。
  • [starti,endi]对应[24,25],[startj,endj]对应[15,24]，发现endj大于等于starti且endi大于等于startj，得到相交区间[max(starti,startj),min(endi,endj)] = [24,24]，加入结果集。
  • 此时endi大于endj，说明区间i向后延伸更长的范围，可能会和下一个区间j有交集，此时需要判断下一个j区间，因此j++向后递进。
  • i = 3，j = 3。
  • [starti,endi]对应[24,25],[startj,endj]对应[25,26]，发现endj大于等于starti且endi大于等于startj，得到相交区间[max(starti,startj),min(endi,endj)] = [25,25]，加入结果集。
  • 此时endj大于endi，说明区间j向后延伸更长的范围，可能会和下一个区间i有交集，此时需要判断下一个i区间，因此i++向后递进。
  • i = 4，j = 3，由于i已经超越数组边界，退出循环。
  • 最终结果为[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

代码实现

    public static int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int fLength = firstList.length,sLength = secondList.length;
        int i = 0,j = 0;
        List<int[]> list = new ArrayList<>();
        while (i < fLength && j < sLength){
            int startI = firstList[i][0],endI = firstList[i][1];
            int startJ = secondList[j][0],endJ = secondList[j][1];
            //只有endJ大于等于startI 且 startJ 大于等于endI 才能证明两者存在交集
            if (endJ >= startI && endI >= startJ ){
                list.add(new int[]{Math.max(startI,startJ),Math.min(endI,endJ)});
            }
            if (endJ < endI){
                j++;
            } else {
                i++;
            }
        }
        return list.toArray(new int[0][0]);
    }

    public static void test(){
        int[][] ints = intervalIntersection(new int[][]{{0, 2}, {5, 10}, {13, 23}, {24, 25}}, new int[][]{{1, 5}, {8, 12}, {15, 24}, {25, 26}});
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
    }