---
title: "253. Meeting Rooms II"
url: "https://laigary.com/interview/coding/253-meeting-rooms-ii"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2024-03-12"
tags: ["Greedy", "Intervals", "Classic"]
---

# 253. Meeting Rooms II

[253\. Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/)

這題我們要算的是，時間有重疊沒有關係，但是告訴我們至少需要幾間會議室，我們才能安排好所有的會議（面試）。

往下閱讀之前，很建議先去看 [252\. Meeting Rooms](/interview/coding/252-meeting-rooms) 。

這裡會假設已經寫過了 [252\. Meeting Rooms](/interview/coding/252-meeting-rooms) 這道題目，那我們就會知道要去看有沒有重疊，最重要的一件事情就是先將時間區間排序好，這樣就可以縮減成用一個條件來判斷時間到底有沒有重疊。

之前的題目只要判斷有沒有重疊就好，可是在這個題目如果有重疊，沒有關係，加開一個會議室就好，所以我們一次可能有很多個會議在進行，我在這裡其實馬上想歪了，覺得這個題目是不要要用遞迴或是動態規劃的方式來做？老實說我也卡住了一陣子。

在這裡也是建議先觀察題目，我的起始思考點我有點難總結，所以我盡可能的描述我的思考過程，希望能幫助到你，不過我希望我的經驗能夠幫助到你。

我開始思考的點是，如果我們現在有幾個會議之前**就已經因為有重疊所以加開會議室了**，我要最大化的利用資源，當我在看我的一個新的時間表的時候，我要怎麼知道我需不需要加開會議室呢？

我在現實生活中會怎麼找？我應該會去找目前哪個會議最早結束，去看看他的結束時間是不是在我的開始時間之前，**如果我已經看了這個，我還有必要去看其他的會議室嗎？不需要了**，因為最早結束的會議都比我的開始的時間還要晚了，那我只能再開一個會議室了。

所以對我重要的資訊是

💡

目前哪個會議室的時間最早結束

到了這裡，我才開始去思考，那什麼樣的資料結構，可以一直幫我讓我知道這個資訊？我在保存這個資訊的時候，還需要考量到什麼？是不是每次有一個新的會議加入，**最早結束時間會改變**？到了這裡才是題目比較困難的地方。

到了這裡我才想到 Heap 就是處理這種情況的最佳幫手？為什麼？

因為我在乎的是一個**極值，是哪個會議結束的最早**，後面如果一直有會議加入，時間結束的很晚很晚，我都不需要考慮啊，因為這個會議室會一直被佔用著，我不可能可以排入會議。

所以當我排序好之後，最一開始會議室一定都是空的，我就排入了第一個會議，並且告訴大家，我的結束時間為何

接著，陸續有一組人要來開會了，我是負責檢查的人，我這時候就檢查一件事情，

1.  這一組人的會議開始時間是不是大於目前最早的會議結束時間，或是恰好在他們結束的時候，如果是，就可以直接進去啦，又因為前一組人已經結束會議了，那我們就可以把那一組的紀錄給清掉了，持續的紀錄目前有在開會的會議室就好了，並且把這組人的的會議結束時間記錄起來。
2.  這一組人的會議開始時間，沒有一間會議室可以用，那好吧，**只好加開一間會議室**，並且把這組人的的會議結束時間記錄起來。

到了這一步，就可以發現我們已經算出了最少要幾間會議室了！

```python
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()

        # 會議室是空的
        heap = []

        # 使用了一間會議室，記錄他們的「結束」時間
        heapq.heappush(heap, intervals[0][1])    
        count = 1

        for i in range(1, len(intervals)):
            # 要來使用會議室的人
            interval = intervals[i]

            # 在所有會議室的結束時間，最早的結束時間有沒有比現在要開會的人的時間還早的？
            if interval[0] >= heap[0]:
                # 有喔，所以我們可以把那組人的時間結束時間給刪掉了
                # 這組人就可以開始使用這個空間
                heapq.heappop(heap)  
            else:
                # 沒有喔，所以目前沒有會議室可以用了，加開一間使用
                count += 1

            # 這組人開始使用會議室了，記錄「結束」時間
            heapq.heappush(heap, interval[1])
        return count

```