leetcode986 区间列表的交集

一时失言乱红尘 2023-07-03 02:49 75阅读 0赞

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

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

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

示例：  
![在这里插入图片描述][format_png]

输入：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

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

思路，双指针，每次先处理前面那个后，再++

class Solution {
        
        public int[][] intervalIntersection(int[][] A, int[][] B) {
        
            List<int[]> res = new ArrayList<>();
    
            int i = 0; // A
            int j = 0; // B
            for (;i < A.length && j < B.length;) {
        
                //  [AAAA]
                //     [bbbb]
                if (A[i][1] <= B[j][1]) {
        
                    if (A[i][1] < B[j][0]) {
        
                        // 相离
                        i++;
                        continue;
                    } else if (A[i][1] == B[j][0]){
        
                        //  相切
                        res.add(new int[]{
        A[i][1],A[i][1]});
                        i++;
                    } else {
        
                        // 相交
                        res.add(new int[]{
        Math.max(A[i][0],B[j][0]),A[i][1]});
                        i++;
                    }
                } else {
        
                //      [aaaa]
                //  [bbbb]
                    if (B[j][1] < A[i][0]) {
        
                        // 相离
                        j++;
                        continue;
                    } else if (B[j][1] == A[i][0]) {
        
                        // 相切
                        res.add(new int[]{
        B[j][1],B[j][1]});
                        j++;
                    } else {
        
                        // 相交
                        res.add(new int[]{
        Math.max(B[j][0],A[i][0]),B[j][1]});
                        j++;
                    }
    
                }
            }
            return res.toArray(new int[0][0]);
        }
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzAyLzAyL2ludGVydmFsMS5wbmc?x-oss-process=image/format,png