LEETCODE 986. Interval List Intersections 解题思路分析

题目大意：

区间列表的交集

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

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

（形式上，闭区间 [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 <= A.length < 1000
• 0 <= B.length < 1000
• 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=986

解题思路分析：

1. 从两个数组的首元素开始循环比较，如果A的右边小于B的左边，说明两个区间不相交，将区间较小（靠左）的A的下标加一。
2. 同理，如果B的右边小于A的左边，两个区间不相交，将区间较小（靠左）的B的下标加一。
3. 排除上述两种情况之后，当前两个区间必有相交的部分，即A与B左边的最大值为相交部分的左边，另外A与B右边的最小值为相交部分的右边。然后将右边较小的一方下标加一。如果两个区间的右边相同，A和B的下标同时加一。
4. 当A或者B的下标越界时，推出循环。

实现代码：

public int[][] intervalIntersection(int[][] A, int[][] B) {
    int indexA=0,indexB=0;
    List<int[]> list=new ArrayList<>();
    while(indexA<A.length&&indexB<B.length){
        int al=A[indexA][0], bl=B[indexB][0];
        int ar=A[indexA][1], br=B[indexB][1];
        if(ar<bl){ // 不相交，A在B左边
            indexA++;
            continue;
        }
        if(br<al){ // 不相交，B在A左边
            indexB++;
            continue;
        }
        int l=Math.max(al,bl); // 相交区间的左边
        int r=Math.min(ar,br); // 相交区间的右边
        list.add(new int[]{l,r});
        if(ar==br){
            indexA++;
            indexB++;
        }else if(ar<br) indexA++;
        else indexB++;
    }
    int[][] res=new int[list.size()][2];
    for(int i=0;i<list.size();i++){
        res[i]=list.get(i);
    }
    return res;
}

本题解法执行时间3ms。

Runtime: 3 ms, faster than 76.53% of Java online submissions for Interval List Intersections.

Memory Usage: 40.2 MB, less than 97.30% of Java online submissions for Interval List Intersections.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-986-interval-list-intersections-解题思路分析/