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