摘要

在這篇文章中，我們將深入探討LeetCode第252題“會議室”的問題，提供一個用Swift編寫的解決方案，并結合實際場景進行分析。通過這篇文章，你將了解如何判斷一個人是否可以參加所有會議，以及相關的時間和空間復雜度分析。

描述

問題描述：給定一個包含多個會議時間間隔的數組，每個間隔由開始時間和結束時間組成，判斷一個人是否可以參加所有的會議。

示例1：

輸入：[[0,30],[5,10],[15,20]]
輸出：false

示例2：

輸入：[[7,10],[2,4]]
輸出：true

題解答案

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

1. 排序：首先，根據會議的開始時間對所有會議進行排序。
2. 檢查重疊：然后，遍歷排序后的會議，檢查當前會議的開始時間是否早于前一個會議的結束時間。如果是，則說明有重疊，返回false。

題解代碼分析

以下是用Swift實現的解決方案：

func canAttendMeetings(_ intervals: [[Int]]) -> Bool {guard intervals.count > 1 else {return true}let sortedIntervals = intervals.sorted { $0[0] < $1[0] }for i in 1..<sortedIntervals.count {if sortedIntervals[i][0] < sortedIntervals[i - 1][1] {return false}}return true
}

代碼分析：

• 邊界檢查：如果會議數量少于2個，直接返回true，因為一個會議或沒有會議都不存在時間沖突的問題。
• 排序：使用sorted方法根據每個會議的開始時間對數組進行排序。
• 遍歷檢查：從第二個會議開始，檢查當前會議的開始時間是否小于前一個會議的結束時間。如果是，說明時間有重疊，返回false。

示例測試及結果

讓我們通過幾個測試用例來驗證上述函數的正確性：

let meetings1 = [[0,30],[5,10],[15,20]]
print(canAttendMeetings(meetings1)) // 輸出：falselet meetings2 = [[7,10],[2,4]]
print(canAttendMeetings(meetings2)) // 輸出：truelet meetings3 = [[1,5],[5,10],[10,15]]
print(canAttendMeetings(meetings3)) // 輸出：true

結果分析：

• 測試用例1：第一個會議和第二個會議時間重疊，因此返回false。
• 測試用例2：所有會議時間無重疊，因此返回true。
• 測試用例3：會議時間首尾相接，但不重疊，因此返回true。

時間復雜度

• 排序：對會議數組進行排序的時間復雜度為O(n log n)，其中n是會議的數量。
• 遍歷檢查：遍歷排序后的數組進行檢查的時間復雜度為O(n)。

因此，總的時間復雜度為O(n log n)。

空間復雜度

如果排序是就地進行的，空間復雜度為O(1)。否則，排序可能需要O(n)的額外空間。

總結

通過對會議時間進行排序并檢查相鄰會議時間是否重疊，我們可以高效地判斷一個人是否可以參加所有會議。這種方法在處理日程安排沖突等實際場景中非常實用。