986. Interval List Intersections

Last updated on Mar 12, 2024

這一題應該算是時間區間的最後一個變形，可以想像成，有兩個人的班表，我們要找出他們哪些時間有一起上班，可能是這個時間這兩個人才可以開會，如果說這個題目問超過兩個人，其實也不會太難，就很像是 N sum 或是 Merger K Linked List 的題目一樣，兩兩的班表慢慢合併，再找出所有重複的區間就可以。

之前的題目主要是找聯集，這是我們想要找到的是時間區間的交集，所以之前的方法這裡不太可以用，另外兩個時間表也都已經排序好了，所以我們這裡也不需要考慮排序的問題，那我們要怎麼取交集呢？

跟之前一樣，我們可以先想想有哪些交集的情況：

[1, 4] , [2, 6] 交集： [2, 4]
[1, 6], [2, 4] 交集： [2, 4]
[1, 3], [3, 6] 交集： [3, 3]

剩下反過來的其實也不用想，因為交集的情況就上面這些，我們就很好觀察出下面的公式，恰巧跟聯集相反。

新區間 = [兩個區間比較晚的開始時間, 兩個區間比較早的開始時間]

到這裡，我們就要想看看，什麼樣的情況，不會造成交集？如果這個交集要成立，那下列這個條件判斷就很重要。

兩個區間比較晚的開始時間 <= 兩個區間比較早的開始時間

接下來就是合併的方法了，我們要找到兩個陣列的時間區間交集，這兩個陣列又不保證一樣長，而且也不可能同時一起前進，因為像是如果有一個員工的時間區間只有一個：但是涵蓋的時間非常的長，而另外一個員工的工作區間都很短，但是卻有好多個工作區間，例如下面：

[[1,10]]
[[1,2], [3,4], [5,6]]

那我們一定是一直去看第二個員工的工作區間，而不是看第一個員工的工作區間，因為他的跨度太廣了，而我們要怎麼判斷他的跨度？基本上就是看結束時間，只要結束時間越遠，就代表另外一個員工的下一個工作時間，就還有可能有重疊。

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        if not firstList or not secondList:
            return []
        i = 0
        j = 0 
        res = []
        while i < len(firstList) and j < len(secondList):
            lo = max(firstList[i][0], secondList[j][0])
            hi = min(firstList[i][1], secondList[j][1])
            if lo <= hi:
                res.append([lo, hi])
            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1
        return res

那如果兩個區間都同時結束呢？其實移動哪一個都沒關係，為什麼？

如果我們先移動第一個陣列的指標，其實就是兩個新的區間重新比較，其實這時候一定不會有任何的重疊，但是沒關係因為當第一個陣列的指標移動了，新陣列的開始時間，一定不可能會是跟第二個陣列的結束時一樣，為什麼呢？因為如果是一樣的話，那這兩個區間早就需要被合併在一起了。

像是下面這樣的例子，絕對不可能存在

[[1,3], [3,4]]
[[2,3], [5,8]]

而是會變成這樣

[[1, 4]]
[[2, 3], [5, 8]]

或至少會是

[[1,3], [4,5]]
[[2,3], [5,8]]

如果 i 從 0 => 1，下一次比較的時候，因為是沒有交集區間的，又因為第二個陣列的結束時間比較早，所以會變成 j 從 0 => 1 ，那這樣就會是 i == 1 and j == 1 這兩個區間的比較與合併。