区间列表的交集

LeetCode 986

区间列表的交集

给定两个由一些 闭区间 组成的列表，每个区间列表都是成对不相交的，并且已经排序。

返回这两个区间列表的交集。

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

示例：

输入：A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

解法：双指针

解题思路：

题目要我们找到两个区间的交集，比如说[0,2]和[1,5]区间的交集就是[1,2],也就是两个区间左取大，右取小，因此我们就用两个指针来遍历这两个数组

指针移动的规则

• 区间的右边较小的指针移动，较大的不移动，因为后面可能还有交集，比如说[1,5]跟区间[0,2]以及区间[5,10]都有交集
• 当两个区间的右边都相同时，同时移动两个指针

代码如下：

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        int Apos=0; //A数组的指针
        int Bpos=0; //B数组的指针
        ArrayList<int[]> res = new ArrayList<int[]>();
        while(Apos<A.length && Bpos<B.length)
        {
            int Astart = A[Apos][0];
            int Aend = A[Apos][1];
            int Bstart = B[Bpos][0];
            int Bend = B[Bpos][1];
            //两个区间的左右边界
            if(Aend<Bend) //有边界小的指针移动
                Apos++;
            else if(Aend>Bend)
                Bpos++;
            else //右边界相同时同时移动
            {
                Apos++;
                Bpos++;
            }
            if(Astart>Bend || Bstart>Aend) 
            //避免出现区间左大右小的情况，如[8,12]和[13,23]
                continue;
            res.add(new int[] {Math.max(Astart,Bstart),Math.min(Aend,Bend)}); 
        }
        int[][] ans = new int[res.size()][2];
        int i=0;
        for(int[] arr : res)
        {
            ans[i][0] = arr[0];
            ans[i][1] = arr[1];
            i++;
        }
        return ans;
    }
}

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/interval-list-intersections
Code）
链接：https://leetcode-cn.com/problems/interval-list-intersections
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。