Time Needed to Inform All Employees
Problem
n employees with headID as the head. manager[i] is the direct manager of i (-1 for head). informTime[i] is how long employee i needs to inform their direct subordinates. Return the time until everyone is informed.
n=7, headID=6, manager=[1,2,3,4,5,6,-1], informTime=[0,6,5,4,3,2,1]21def num_of_minutes(n, headID, manager, informTime):
children = [[] for _ in range(n)]
for i, m in enumerate(manager):
if m != -1: children[m].append(i)
def dfs(u):
if not children[u]: return 0
return informTime[u] + max(dfs(c) for c in children[u])
return dfs(headID)function numOfMinutes(n, headID, manager, informTime) {
const children = Array.from({length: n}, () => []);
for (let i = 0; i < n; i++) if (manager[i] !== -1) children[manager[i]].push(i);
function dfs(u) {
if (!children[u].length) return 0;
let best = 0;
for (const c of children[u]) best = Math.max(best, dfs(c));
return informTime[u] + best;
}
return dfs(headID);
}class Solution {
List> ch;
int[] inf;
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
ch = new ArrayList<>();
for (int i = 0; i < n; i++) ch.add(new ArrayList<>());
for (int i = 0; i < n; i++) if (manager[i] != -1) ch.get(manager[i]).add(i);
inf = informTime;
return dfs(headID);
}
int dfs(int u) {
if (ch.get(u).isEmpty()) return 0;
int best = 0;
for (int c : ch.get(u)) best = Math.max(best, dfs(c));
return inf[u] + best;
}
} int numOfMinutes(int n, int headID, vector& manager, vector& informTime) {
vector> ch(n);
for (int i = 0; i < n; i++) if (manager[i] != -1) ch[manager[i]].push_back(i);
function dfs = [&](int u) -> int {
if (ch[u].empty()) return 0;
int best = 0;
for (int c : ch[u]) best = max(best, dfs(c));
return informTime[u] + best;
};
return dfs(headID);
} Explanation
The company is really a tree: the head is the root and each employee's manager is its parent. A manager can only finish informing everyone once their slowest branch finishes, so the answer is the longest weighted path from the head down to a leaf.
First we flip the manager array around to build a children list, so each manager knows who they directly inform. We do this by scanning every employee i and adding it under children[manager[i]].
Then dfs(u) computes how long it takes for everyone below u to be informed. A leaf needs 0. Otherwise u spends informTime[u] to alert its subordinates, and we add the maximum of the subtrees, because all branches start informing at the same time and we wait for the slowest.
Example: headID=6 with the chain 6→5→4→3→2→1→0. The inform times stack up along the single path as 1+2+3+4+5+6 = 21.
We visit each employee once, so the time is O(n).