主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)整數(shù) n。代表現(xiàn)在有編號(hào)為 0 到 n - 1 的 n 間房間。
你被給定一個(gè)二維整數(shù)陣列 meetings，其中 meetings[starti, endi] 代表著有一場(chǎng)會(huì)議將會(huì)在半閉時(shí)間區(qū)間 [starti, endi) 的時(shí)候舉辦。所有 starti 之?dāng)?shù)值彼此相異。
會(huì)議將會(huì)根據(jù)以下方式分配到各個(gè)房間：
每場(chǎng)會(huì)議將會(huì)舉辦於有著最小編號(hào)的未佔(zhàn)用房間。
如果現(xiàn)在沒(méi)有空房間，則該會(huì)議將會(huì)被延期直到有房間空出來(lái)為止。被延後的會(huì)議之持續(xù)時(shí)間應(yīng)與原本相同。
當(dāng)有一間房變?yōu)槲磥?zhàn)用的狀態(tài)，有著最早開始時(shí)間的會(huì)議應(yīng)被提供該房間。
回傳有最多場(chǎng)會(huì)議舉行的房間為何。如果有多間房間，則回傳編號(hào)最小者。
一個(gè)半閉區(qū)間 [a, b) 為一個(gè)介於 a 到 b 之間，其中端點(diǎn) a 有包含在內(nèi)，但 b 則無(wú)。
限制：
1 ≦ n ≦ 100
1 ≦ meetings.length ≦ 10 ^ 5
meetings[i].length == 2
0 ≦ starti < endi ≦ 5 × 10 ^ 5
所有 starti 之?dāng)?shù)值彼此相異。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
輸出： 0
解釋：
- 在時(shí)間點(diǎn) 0，兩個(gè)房間都沒(méi)被佔(zhàn)用。第一場(chǎng)會(huì)議舉行於房間 0。
- 在時(shí)間點(diǎn) 1，只有房間 1 沒(méi)被佔(zhàn)用。第二場(chǎng)會(huì)議舉行於房間 1。
- 在時(shí)間點(diǎn) 2，兩個(gè)房間都被佔(zhàn)用了。第三場(chǎng)會(huì)議被延期。
- 在時(shí)間點(diǎn) 3，兩個(gè)房間都被佔(zhàn)用了。第四場(chǎng)會(huì)議被延期。
- 在時(shí)間點(diǎn) 5，位於房間 1 的會(huì)議開完了。第三場(chǎng)會(huì)議舉行於房間 1，其時(shí)間段為 [5,10)。
- 在時(shí)間點(diǎn) 10，位於兩個(gè)房間的會(huì)議都開完了。第四場(chǎng)會(huì)議舉行於房間 0，其時(shí)間段為 [10,11)。
房間 0 和房間 1 都舉行了兩場(chǎng)會(huì)議，所以我們回傳 0。
範(fàn)例 2：
輸入： n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
輸出： 1
解釋：
- 在時(shí)間點(diǎn) 1，三間房間都沒(méi)被佔(zhàn)用。第一場(chǎng)會(huì)議將舉行於房間 0。
- 在時(shí)間點(diǎn) 2，房間 1 和 2 都沒(méi)被佔(zhàn)用。第二場(chǎng)會(huì)議將舉行於房間 1。
- 在時(shí)間點(diǎn) 3，只有房間 2 沒(méi)有被佔(zhàn)用。第三場(chǎng)會(huì)議將舉行於房間 2。
- 在時(shí)間點(diǎn) 4，所有房間都被佔(zhàn)用了。第四場(chǎng)會(huì)議被延期。
- 在時(shí)間點(diǎn) 5，位於房間 2 的會(huì)議開完了。第四場(chǎng)會(huì)議舉行於房間 2，其時(shí)間段為 [5,10)。
- 在時(shí)間點(diǎn) 6，所有房間都被佔(zhàn)用了。第五場(chǎng)會(huì)議被延期。
- 在時(shí)間點(diǎn) 10，位於房間 1 和 2 的會(huì)議都開完了。第五場(chǎng)會(huì)議舉行於房間 1，其時(shí)間段為 [10,12)。
房間 1 舉行了 1 場(chǎng)會(huì)議，而房間 1 和 2 各舉行了 2 場(chǎng)，所以我們回傳 1。
解題思維：
模擬即可。
所以我們需要什麼？很明顯的，我們會(huì)先需要記錄哪些房間目前有被佔(zhàn)用、目前已經(jīng)開了多少場(chǎng)會(huì)議。
此外，為了決定之後哪些會(huì)議如果要延後時(shí)程的話需要延後到哪個(gè)時(shí)刻，我們需要記錄所有現(xiàn)在正在開的會(huì)議之結(jié)束時(shí)間。而可以看到先結(jié)束的會(huì)被後來(lái)的會(huì)議取代，因此這邊記錄用的資料結(jié)構(gòu)需要?jiǎng)討B(tài)地維護(hù)所有結(jié)束時(shí)間中的最小值，而優(yōu)先佇列（Priority Queue）可以勝任這個(gè)任務(wù)。
以上，稱記錄佔(zhàn)用情況的陣列為 U、已經(jīng)開的會(huì)議數(shù)量之陣列為 C、維護(hù)結(jié)束時(shí)間最小值（連同房間編號(hào)）的優(yōu)先佇列為 PQ。
接著是對(duì)資料本身進(jìn)行處理。根據(jù)題目敘述可以看到我們應(yīng)當(dāng)按照著開始時(shí)間的早晚來(lái)安排房間（越早開始的越早分配到房間）。而題目沒(méi)有保證給定的會(huì)議時(shí)間們將會(huì)依照開始時(shí)間來(lái)排序，因此我們需要自行依據(jù)開始時(shí)間由早到晚排序。
接著掃過(guò)排序後的每一場(chǎng)會(huì)議：
假設(shè)現(xiàn)在看到的是會(huì)議 m，其時(shí)間區(qū)間為 [L, R)。而如果現(xiàn)在可以看到如果 PQ 中的最小值（最早結(jié)束的會(huì)議）是先於 m 之開始，即「最早的結(jié)束時(shí)間」 ≦ L，則 m 將會(huì)開在這個(gè)結(jié)束掉的會(huì)議之房間。其中判斷條件有「=」之情況是因?yàn)闀?huì)議的時(shí)間是半閉區(qū)間，因此結(jié)束時(shí)間本身可以塞另一個(gè)會(huì)議的開始；又或是 PQ 中的元素?cái)?shù)量以及到達(dá) n 了，也就是所有房間都被佔(zhàn)用了，因此必須把最早結(jié)束的會(huì)議之房間空出來(lái)。
如果上述情況只有後者的條件有被滿足（全房間佔(zhàn)滿），則代表最早結(jié)束的時(shí)間（稱其為 X）是大於 L 的。因此我們需要額外把 m 的時(shí)間區(qū)間調(diào)整至 [X, X + (R - L))。
不管上述情況有無(wú)發(fā)生，總之現(xiàn)在的階段必定有房間可以用（記得前面條件符合要把 U 的對(duì)應(yīng)位置清掉，以代表該房間空了）。因此我們由編號(hào) 0 掃到編號(hào) n - 1，看哪間房間可以用即可（用陣列 U 的數(shù)值判斷）。假設(shè)找到的是房間 i，則我們需要把 C[i] 加 1，代表房間 i 多開了一場(chǎng)會(huì)議。接著把 m 的結(jié)束時(shí)間（可能是原本的 R，又或是 X + (R - L)，取決於前面的條件有無(wú)符合）以及使用的房間編號(hào)放到 PQ 中。
重複以上步驟直到掃過(guò)所有房間為止。最後只要掃過(guò)一次陣列 C，看哪個(gè)房間的會(huì)議最多即可。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
