1376. Time Needed to Inform All Employees

Medium
Description

一家公司有 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#

本質是一棵多叉樹，求從根到所有葉節點的最長路徑。

  • 組織架構就是一棵以 headID 為根的多叉樹
  • 通知是從上而下傳播的，每個主管同時通知所有下屬
  • 總時間就是根到所有葉節點路徑中，時間總和最大的那條

Approaches#

1: 建圖 + DFS#

  • 概念: 先用鄰接表建圖，再從根 DFS，求最長路徑的通知時間
  • 時間複雜度: O(n)
  • 空間複雜度: 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: 自底向上（不建圖）#

  • 概念: 對每個葉節點，沿著 manager 陣列往上累加時間到根，用快取避免重複計算
  • 時間複雜度: O(n)
  • 空間複雜度: 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 自然適合
  • 關鍵技巧: 自底向上方法可以省去建圖步驟，用 memoization 確保每個節點只計算一次