1376. Time Needed to Inform All Employees

1376. Time Needed to Inform All Employees

題意

• 每個員工有一位直屬上司（除了公司的頭頭，以-1表示）

• 每位員工通知其直屬下屬所需的時間都是已知的

• 要求計算從最高頭頭通知到每位員工所需的總時間

限制

• 1 <= n <= 10^5

• 0 <= headID < n

• manager.length == n

• 0 <= manager[i] < n

• manager[headID] == -1

• informTime.length == n

• 0 <= informTime[i] <= 1000

• informTime[i] == 0 if employee i has no subordinates.

• It is guaranteed that all the employees can be informed.

思考

• 建立員工樹：

  • 遍歷每位員工，若該員工有上司（manager[i] != -1），則在 unordered_map 中記錄該上司對應的下屬員工

  • 這種方式可以快速建立起一個從上司到下屬的多子節點 tree

• 使用DFS

  • 從頭頭（headID）開始，遞迴訪問每個下屬，計算從該員工通知到其所有下屬所需的時間

  • 對於每位員工，他所需的總通知時間是他本身的通知時間加上他所有下屬所需的最大通知時間

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);
    }
};