一、題目

給定兩個由一些 閉區(qū)間 組成的列表，每個區(qū)間列表都是成對不相交的，并且已經(jīng)排序。
返回這兩個區(qū)間列表的交集。
（形式上，閉區(qū)間 [a, b]（其中 a <= b）表示實數(shù) x 的集合，而 a <= x <= b。兩個閉區(qū)間的交集是一組實數(shù)，要么為空集，要么為閉區(qū)間。例如，[1, 3] 和 [2, 4] 的交集為 [2, 3]。）

image.png

提示：
1、0 <= A.length < 1000
2、0 <= B.length < 1000
3、0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

https://leetcode-cn.com/problems/interval-list-intersections/

二、解題思路

整體思路

bug free啊
糾正思路很重要
1、原有做題思路（為什么思路這么復雜）
圖1
2、正確的思路
圖2
自頂向下的思路：
（1）大方向：有交集、無交集
--> 代碼1
（2）有交集：共同點，代碼層面
--> 代碼2
（3）迭代更新
圖3-7

image.png

image.png

image.png

image.png

image.png

image.png

image.png

關(guān)鍵問題：正確的分析思路

第一步
第二步

三、題解

暴力解法

題解1:

錯誤解法

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        int nA = A.length;
        int nB = B.length;
        List<int[]> res = new ArrayList<>();
        int i = 0, j = 0, left = 0, right = 0;
        while (i < nA && j < nB) {
            if (A[i][1] < B[j][0] || A[i][0] > B[j][1]) {
                // 無交集
                i++;
                // j++;
            }else { // 有交集
                left = Math.max(A[i][0], B[j][0]);
                right = Math.min(A[i][1], B[j][1]);
                res.add(new int[]{left, right});
                if (B[j][1] < A[i][1]) {
                    j++;
                }else {
                    i++;
                }
            }
        }
        return res.toArray(new int[0][]);
    }
}

易錯：無交集部分的指針迭代不對

正確做法：

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        int nA = A.length;
        int nB = B.length;
        List<int[]> res = new ArrayList<>();
        int i = 0, j = 0, left = 0, right = 0;
        while (i < nA && j < nB) {
            if (A[i][1] < B[j][0] || A[i][0] > B[j][1]) {
                // 無交集
                // i++;
                // j++;
                if (B[j][1] < A[i][1]) {
                    j++;
                }else {
                    i++;
                }
            }else { // 有交集
                left = Math.max(A[i][0], B[j][0]);
                right = Math.min(A[i][1], B[j][1]);
                res.add(new int[]{left, right});
                if (B[j][1] < A[i][1]) {
                    j++;
                }else {
                    i++;
                }
            }
        }
        return res.toArray(new int[0][]);
    }
}

結(jié)果

執(zhí)行用時：4 ms, 在所有 Java 提交中擊敗了95.25%的用戶
內(nèi)存消耗：40.5 MB, 在所有 Java 提交中擊敗了81.95%的用戶

復雜度分析

時間復雜度：O(n)
空間復雜度：O(1)

四、測試數(shù)據(jù)

[[0,2],[5,10],[13,23],[24,25]]
[[1,5],[8,12],[15,24],[25,26]]

參考

1、題解參考
https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/qu-jian-jiao-ji-wen-ti

2、優(yōu)秀題解