LeetCode - Meeting Rooms（會議室）

題目描述

給定一個由會議時間區間組成的數組 intervals，其中每個區間 intervals[i] = [start, end] 表示會議的開始和結束時間，請判斷一個人是否可以參加所有會議。如果任何兩個會議之間有重疊，則返回 False，否則返回 True。

範例：

輸入：intervals = [[0,30],[5,10],[15,20]]
輸出：False
解釋：會議 [0,30] 與 [5,10] 和 [15,20] 有重疊。

輸入：intervals = [[7,10],[2,4]]
輸出：True
解釋：會議沒有重疊。

解法思路

要判斷是否可以參加所有會議，關鍵在於檢查會議時間區間之間是否有重疊。具體步驟如下：

1. 按開始時間排序：首先將會議區間根據開始時間進行排序，這樣可以確保相鄰的會議之間只需檢查結束和開始時間是否重疊。

2. 檢查重疊：遍歷排序後的會議列表，檢查每個會議區間是否與下一個會議區間重疊。如果當前會議的結束時間大於下一個會議的開始時間，則說明會議時間有重疊，無法參加所有會議，返回 False。如果遍歷結束沒有發現重疊，則返回 True。

範例代碼

以下是 Python 的實現：

def canAttendMeetings(intervals):
    # 1. 將會議時間按照開始時間排序
    intervals.sort(key=lambda x: x[0])
    
    # 2. 檢查是否有重疊
    for i in range(1, len(intervals)):
        # 如果前一個會議的結束時間大於當前會議的開始時間，則會議重疊
        if intervals[i-1][1] > intervals[i][0]:
            return False
    
    return True

代碼解析

1. 排序會議時間區間：根據會議開始時間排序，這樣可以逐一檢查相鄰會議是否有重疊。
2. 檢查重疊：遍歷排序後的區間列表，檢查相鄰會議是否重疊。如果發現任何一組會議的結束和開始時間重疊，則返回 False。
3. 返回結果：如果遍歷結束時沒有發現重疊，則返回 True。

時間和空間複雜度

• 時間複雜度：O(n log n)，主要來自於排序操作，其中 n 是會議區間的數量。
• 空間複雜度：O(1)，因為只使用了常數額外空間進行比較和遍歷。