題目資訊

• 題目編號: 3169
• 題目連結: Count Days Without Meetings
• 主題: Array, Sorting

題目敘述

你得到一個正整數 days，表示員工可用來工作的總天數（從第 1 天開始）。你也得到一個大小為 $n$ 的二維陣列 meetings，其中，$meetings[i] = [start_i, end_i]$ 代表會議 $i$ 的開始和結束天數（包含在內）。

返回員工可用來工作但未安排會議的天數。

注意： 會議可能重疊。

範例 1:

輸入： days = 10, meetings = [[5,7],[1,3],[9,10]]

輸出： 2

解釋：

第 4 和第 8 天沒有安排會議。

範例 2:

輸入： days = 5, meetings = [[2,4],[1,3]]

輸出： 1

解釋：

第 5 天沒有安排會議。

範例 3:

輸入： days = 6, meetings = [[1,6]]

輸出： 0

解釋：

所有工作日都安排了會議。

限制條件：

• $1 \leq days \leq 10^9$
• $1 \leq meetings.length \leq 10^5$
• $meetings[i].length == 2$
• $1 \leq meetings[i][0] \leq meetings[i][1] \leq days$

直覺

問題涉及找出員工在不排定會議的情況下可供工作的天數。由於會議時間可能重疊，我們的想法是找出這些會議間的空閒天數。通過排序並依序分析會議，我們可以有效地跟蹤這些空隙，從而確定所需的空閒天數數量。

解法

此解法可以分為幾個關鍵步驟：

1. 初始化：首先設置兩個主要變量：availableDays （用來計算員工空閒的天數）和 lastEndDay （用來跟蹤已處理會議的最後結束日）。

2. 排序：將會議按開始日進行排序，這樣可以逐一處理會議並簡化地識別會議之間的間隙。

3. 添加虛擬會議：在會議列表中附加一個虛擬會議 (totalDays + 1, totalDays + 1)。這使得在處理循環中，任何最後一個真實會議之後的空閒期都可以被統一處理，避免了在循環後的單獨邏輯。

4. 迭代和計算：

   • 對於每個會議，計算 lastEndDay 和當前會議開始日 (meeting[0]) 之間的空閒天數。使用公式 meeting[0] - lastEndDay - 1 來確定會議之間可用的天數。max 函數確保當會議重疊或相連時不會添加負值。
   • 將 lastEndDay 更新為其當前值與當前會議結束日 (meeting[1]) 兩者中的最大值。這樣可以持續跟蹤遇到的最晚結束日。

5. 返回結果：一旦所有會議均已處理完畢，availableDays 則持有員工在沒有參與任何會議時空閒的天數總計。此值作為結果返回。

該算法有效地處理了問題限制條件，通過排序（在給定的限制下是可行的）和對會議的一次遍歷操作，總體複雜度主要由排序步驟 (O(n \log n)) 決定，其中 (n) 是會議的數量。這使得該解決方案在提供的限制範圍內具有可擴展性。

程式碼

C++

class Solution {
public:
    int countDays(int totalDays, vector<vector<int>>& meetings) {
        // 用於儲存沒有會議安排的可用天數計數
        int availableDays = 0;
        
        // 用於追蹤考慮過的會議的最後結束日
        int lastEndDay = 0;
        
        // 依照會議的開始日排序，以確保按順序處理
        sort(meetings.begin(), meetings.end());
        
        // 添加一個虛擬會議超過最後一天以簡化邏輯
        meetings.push_back({totalDays + 1, totalDays + 1});
        
        // 遍歷每個會議
        for (vector<int>& meeting : meetings) {
            // 計算並加總上次會議和當前會議之間的空閒天數
            availableDays += max(meeting[0] - lastEndDay - 1, 0);
            
            // 更新最後的結束日為目前遇到的最大結束日
            lastEndDay = max(lastEndDay, meeting[1]);
        }
        
        // 返回沒有會議安排的可用天數總計
        return availableDays;
    }
};

Python

class Solution:
    def countDays(self, totalDays, meetings):
        # 用於儲存沒有會議安排的可用天數計數
        availableDays = 0
        
        # 用於追蹤考慮過的會議的最後結束日
        lastEndDay = 0
        
        # 依照會議的開始日期排序以確保順序處理
        meetings.sort()
        
        # 添加一個虛擬會議在最後一天之後以簡化邏輯
        meetings.append([totalDays + 1, totalDays + 1])
        
        # 遍歷每個會議
        for meeting in meetings:
            # 計算並累加上一個會議和當前會議之間的空閒天數
            availableDays += max(meeting[0] - lastEndDay - 1, 0)
            
            # 更新lastEndDay為目前為止遇到的最大結束日
            lastEndDay = max(lastEndDay, meeting[1])
        
        # 返回總的空閒可用天數
        return availableDays

複雜度分析

• 時間複雜度: $O(n \log n)$

  時間複雜度主要由排序步驟主導，其複雜度為 $O(n \log n)$，其中 $n$ 是會議的數量。將會議列表按開始日期排序是此演算法中計算量最大的操作。遍歷會議和計算可用天數兩者皆在線性時間 $O(n)$ 內完成。因此，總體的時間複雜度仍為 $O(n \log n)$。

• 空間複雜度: $O(1)$

  空間複雜度為 $O(1)$，因為演算法使用的額外空間量是固定的，與輸入大小無關。像 availableDays、lastEndDay 這樣的變數，以及一些臨時存儲空間，並不會隨著輸入大小而增長。在會議列表末尾添加一個固定的額外元素仍然會導致空間複雜度為 $O(1)$。