一家公司有 n 位員工，每位員工有一位直屬主管（除了總經理）。給定總經理 headID、每位員工的主管 manager[]，以及每位主管通知直屬下屬所需時間 informTime[]。回傳通知所有員工所需的總時間。
Example:
Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0] Output: 1
Intuition
TIP
本質是一棵多叉樹，求從根到所有葉節點的最長路徑。
- 組織架構就是一棵以 headID 為根的多叉樹
- 通知是從上而下傳播的，每個主管同時通知所有下屬
- 總時間就是根到所有葉節點路徑中，時間總和最大的那條
Approaches
1. Build Graph + DFS — O(n) / O(n)
- Idea: 先用鄰接表建圖，再從根 DFS，求最長路徑的通知時間
- Time:
O(n) - Space:
O(n)
class Solution {
fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
val children = Array(n) { mutableListOf<Int>() }
for (i in 0 until n) {
if (manager[i] != -1) {
children[manager[i]].add(i)
}
}
return dfs(headID, children, informTime)
}
private fun dfs(node: Int, children: Array<MutableList<Int>>, informTime: IntArray): Int {
var maxTime = 0
for (child in children[node]) {
maxTime = maxOf(maxTime, dfs(child, children, informTime))
}
return informTime[node] + maxTime
}
}⭐ 2. Bottom-Up (no graph) — O(n) / O(n)
- Idea: 對每個葉節點，沿著 manager 陣列往上累加時間到根，用快取避免重複計算
- Time:
O(n) - Space:
O(n)
class Solution {
fun numOfMinutes(n: Int, headID: Int, manager: IntArray, informTime: IntArray): Int {
val memo = IntArray(n) { -1 }
memo[headID] = 0
var result = 0
for (i in 0 until n) {
result = maxOf(result, dfs(i, manager, informTime, memo))
}
return result
}
private fun dfs(i: Int, manager: IntArray, informTime: IntArray, memo: IntArray): Int {
if (memo[i] != -1) return memo[i]
memo[i] = informTime[manager[i]] + dfs(manager[i], manager, informTime, memo)
return memo[i]
}
}🔑 Takeaways
- Pattern: 多叉樹求根到葉的最長路徑，DFS 自然適合
- Key trick: 自底向上方法可以省去建圖步驟，用 memoization 確保每個節點只計算一次