---
title: "986. Interval List Intersections"
url: "https://laigary.com/interview/coding/986-interval-list-intersections"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2024-03-12"
tags: ["Intervals", "Classic"]
---

# 986. Interval List Intersections

[986\. Interval List Intersections](https://leetcode.com/problems/interval-list-intersections/)

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

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

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

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

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

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

```

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

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

```

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

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

```

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

```python
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

```

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

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

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

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

```

而是會變成這樣

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

```

或至少會是

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

```

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