252. Meeting Rooms

252. Meeting Room

這個題目是所有題目的基礎,題目給定一連串的時間序列,且時間序列是亂序的,想問這些時間區間有沒有重複?

雖然說題目是簡單,我覺得這只是題目的解法很簡單,但是如果第一次看到題目,到底要從哪裡開始想,我覺得還是有挑戰性的。

面試遇到不會的題目,就是先冷靜觀察,先看看如果我們只有兩個區間,我們要如何判斷時間有重疊?

  • [1, 6] 和 [2, 5]:前面的區間誇度大,區間大到包含了後面的所有時間區間。
  • [1, 4] 和 [2, 5]:前一個的區間,剛好跨過了後一個區間的開始時間。
  • [3, 6] 和 [2, 5]:前一個的區間,剛好從後面區間的中間開始。
  • [3, 4] 和 [2, 5]:前一個區間跨度小,區間剛好被後面的所有區間包含。
  • [1, 3] 和[3,6]:前一個區間的時間結束時間與後一個時間區間的開始時間相同,不算是重疊

我當時觀察到這裡,其實開始想了一下自己的解法對不對,一次比兩個區間很簡單,但是整個數列的區間都是亂排的,我要怎麼樣都全部比完呢?是不是有什麼地方我沒有想到?

💡
我覺得在面試的時候最怕的就是這種情況,我們按照題目的敘述開始展開思路,但是到底我們的思路對不對?其實在真的寫完之前,都不知道,不過其實真正面試時遇到的題目,很少很少會出現需要「跳脫思考」的題目,如果有公司真的喜歡出這種題目,就算是夢想公司我也會希望當下不要覺得要太難過,因為30~45分中就要想出跳脫思考,這表示這間公司的選人來說是的標準是不可觀的。真的遇到這樣的情況,反而應該要先問問面試官,我想的方向對不對就好?

這個題目的難度不高,其實不會到想不到解法啦,上面的話只是給自己信心,要相信自己可以在面試中表現好,回到題目繼續觀察,其實第三、第四點,如果我們把前後的區間對調,滿足他們重疊的情況,就會變成一模一樣了,我在第一次寫題目的當下就覺得是人腦在思考時有時候太快,反而讓我自己產生了盲點。

於是這類型題目最重要的一個轉折點就出現了,那就是如果我們可以把所有的時間區間,先不用管結束時間,而是以按照開始的時間為基準,由小到大排列,那我們就可以用另外一個條件來判斷時間是否重疊,那就是:

💡
前一個時間區間的結束時間,不能大於後一個時間區間的開始時間

題目其實就簡化成了另一個問題,如何將題目的時間區間按照開始時間由小到大排列。這邊最後的題目我使用了 python 預設的 sort() 語法來做到,不過在面試的時候,可能會不知道原來 python 的 sort() 可以滿足這樣的需求,但是這也沒有問題,因為 heap 的用法就是面試前一定要準備到的,也可以使用 heap 來重新去做到排序。

因此只要時間排序好了,就可以用上面的判斷式直接去回答題目的問題了。

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        if not intervals:
            return True
        intervals.sort()

        for i in range(1, len(intervals)):
            previous_begin_time, previous_end_time = intervals[i - 1]
            current_begin_time, current_end_time = intervals[i]
            if current_begin_time < previous_end_time:
                return False

        return True