253. Meeting Rooms II
這題我們要算的是，時間有重疊沒有關係，但是告訴我們至少需要幾間會議室，我們才能安排好所有的會議（面試）。
往下閱讀之前，很建議先去看 252. Meeting Rooms 。
這裡會假設已經寫過了 252. Meeting Rooms 這道題目，那我們就會知道要去看有沒有重疊，最重要的一件事情就是先將時間區間排序好，這樣就可以縮減成用一個條件來判斷時間到底有沒有重疊。
之前的題目只要判斷有沒有重疊就好，可是在這個題目如果有重疊，沒有關係，加開一個會議室就好，所以我們一次可能有很多個會議在進行，我在這裡其實馬上想歪了，覺得這個題目是不要要用遞迴或是動態規劃的方式來做？老實說我也卡住了一陣子。
在這裡也是建議先觀察題目，我的起始思考點我有點難總結，所以我盡可能的描述我的思考過程，希望能幫助到你，不過我希望我的經驗能夠幫助到你。
我開始思考的點是，如果我們現在有幾個會議之前就已經因為有重疊所以加開會議室了，我要最大化的利用資源，當我在看我的一個新的時間表的時候，我要怎麼知道我需不需要加開會議室呢？
我在現實生活中會怎麼找？我應該會去找目前哪個會議最早結束，去看看他的結束時間是不是在我的開始時間之前，如果我已經看了這個，我還有必要去看其他的會議室嗎？不需要了，因為最早結束的會議都比我的開始的時間還要晚了，那我只能再開一個會議室了。
所以對我重要的資訊是
到了這裡，我才開始去思考，那什麼樣的資料結構，可以一直幫我讓我知道這個資訊？我在保存這個資訊的時候，還需要考量到什麼？是不是每次有一個新的會議加入，最早結束時間會改變？到了這裡才是題目比較困難的地方。
到了這裡我才想到 Heap 就是處理這種情況的最佳幫手？為什麼？
因為我在乎的是一個極值，是哪個會議結束的最早，後面如果一直有會議加入，時間結束的很晚很晚，我都不需要考慮啊，因為這個會議室會一直被佔用著，我不可能可以排入會議。
所以當我排序好之後，最一開始會議室一定都是空的，我就排入了第一個會議，並且告訴大家，我的結束時間為何
接著，陸續有一組人要來開會了，我是負責檢查的人，我這時候就檢查一件事情，
- 這一組人的會議開始時間是不是大於目前最早的會議結束時間，或是恰好在他們結束的時候，如果是，就可以直接進去啦，又因為前一組人已經結束會議了，那我們就可以把那一組的紀錄給清掉了，持續的紀錄目前有在開會的會議室就好了，並且把這組人的的會議結束時間記錄起來。
- 這一組人的會議開始時間，沒有一間會議室可以用，那好吧，只好加開一間會議室，並且把這組人的的會議結束時間記錄起來。
到了這一步，就可以發現我們已經算出了最少要幾間會議室了！
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