Time Needed to Inform All Employees

Intuition

Solution

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        adj = [[] for _ in range(n)]
        for i, manager_i in enumerate(manager):
            if manager_i != -1:
                adj[manager_i].append(i)

        return self._dfs(headID, adj, informTime, 0)

    def _dfs(self, current, adj, informTime, currentTime):
        timeCost = currentTime
        for child in adj[current]:
            timeCost = max(
                self._dfs(child, adj, informTime, currentTime + informTime[current]),
                timeCost
            )
        return timeCost