2 min read leetcode

1376. Time Needed to Inform All Employees

1376. Time Needed to Inform All Employees
Photo by Markus Spiske / Unsplash

題目連結: 1376. Time Needed to Inform All Employees

題意解析

  • 每個員工都有一位直屬上司（除了公司的最高主管 headID，用 -1 表示）。
  • 每位員工通知其直屬下屬所需的時間 informTime[i] 已知。
  • 目標是計算從 headID 開始，通知所有員工所需的最長時間。

題目限制

  • 1 <= n <= 10^5
  • 0 <= headID < n
  • manager.length == n
  • 0 <= manager[i] < n 或 manager[i] == -1（headID）
  • informTime.length == n
  • 0 <= informTime[i] <= 1000
  • informTime[i] == 0 若員工 i 沒有下屬
  • 保證所有員工都能被通知

解題思路

1. 建立員工樹

我們可以使用 鄰接表 來建立員工關係：

  • 遍歷 manager[i]，如果 manager[i] != -1，則在 map[manager[i]] 中記錄 i 作為其下屬。
  • 這樣，我們就能夠快速構建一個從 上司到下屬的樹狀結構。

2. 使用 DFS 來計算最長通知時間

  • 從 headID 開始，對每位員工遞迴訪問其所有下屬，計算 最大通知時間。
  • 若 employee i 有下屬，則 i 需要花費 informTime[i] 的時間通知他們。
  • 公式：$$totalTime[i]=informTime[i]+max⁡(totalTime[j]∣j 是 i 的下屬)$$

Solution

class Solution {
    int dfs(int i, unordered_map<int, vector<int>>& map, vector<int>& informTime) {
        int time = 0;
        for (const int sub : map[i]) {
            time = max(time, dfs(sub, map, informTime));
        }
        return informTime[i] + time;
    }
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        unordered_map<int, vector<int>> map;
        for (int i = 0; i < n; i += 1) {
            if (manager[i] != -1) {
                map[manager[i]].push_back(i);
            }
        }

        return dfs(headID, map, informTime);
    }
};

時間與空間複雜度分析

時間複雜度

  • 建構員工樹 需要遍歷 manager 陣列 一次，為 O(n)。
  • DFS 遍歷員工樹：
    • 每個節點 最多 被訪問 一次，時間複雜度也是 O(n)。
  • 總時間複雜度： O(n)

空間複雜度

  • 儲存員工關係的 unordered_map<int, vector<int>>：
    • 最壞情況下，每個員工有唯一的上司，形成 鏈狀結構，則 unordered_map 需要儲存 O(n) 的鍵值對。
  • 遞迴堆疊空間：
    • 最壞情況（鏈狀結構）：遞迴深度為 O(n)。
    • 最佳情況（平衡樹）：遞迴深度為 O(log⁡n)。
  • 總空間複雜度為 O(n)（主要來自 unordered_map 和 DFS 的堆疊空間）。

Justin