MediumRating 1561
1376. Time Needed to Inform All Employees
treedepth-first-searchbreadth-first-search
解題說明
Time Needed to Inform All Employees
題目描述:
一家公司有 n 個員工,從 0 到 n-1 編號。headID 是總經理。manager[i] 是第 i 個員工的直屬上司,informTime[i] 是第 i 個員工通知所有直屬下屬所需的時間。總經理的 manager[headID] = -1。求總經理通知所有員工所需的總時間。
解題思路:
這本質上是一棵以 headID 為根的樹。我們需要找出從根到所有葉節點的最長路徑(路徑上的 informTime 之和)。使用 DFS 遍歷:先建立鄰接表(上司 → 下屬列表),然後從根節點開始 DFS,對每個節點,遞迴計算通知其所有子樹的最大時間,加上該節點自身的 informTime。答案就是根節點的 DFS 結果。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每個節點恰好訪問一次。
空間複雜度:O(n) — 鄰接表 O(n) 加上遞迴堆疊深度最壞 O(n)。
虛擬碼
1. Build adjacency list: for each employee i, add i to children[manager[i]]
2. DFS(node):
a. maxTime = 0
b. For each child in children[node]:
- maxTime = max(maxTime, DFS(child))
c. Return informTime[node] + maxTime
3. Return DFS(headID)其他解法
BFS 層序遍歷:從根節點開始 BFS,佇列存放 (節點, 累計時間) 對。每層將 informTime 加到累計時間上。追蹤全局最大累計時間。時間 O(n),空間 O(n)。
自底向上 DFS(無需建樹):從每個葉節點往上走到根,累加路徑上的 informTime。搭配記憶化避免重複計算。時間 O(n),但常數較大且不如建樹直觀。
延伸思考
- 若每個員工通知不同下屬的時間不同(而非同時通知所有下屬),如何修改?
- 若要找出最後被通知到的員工是誰(而非只求時間),如何修改?
- 若公司結構不是樹而是有向無環圖(DAG),如何求解?