#1376

Time Needed to Inform All Employees

specialist · 710 · lc medium +30 · verified · 60.4% accepted · 4,249 likes · top 59%

⚑ DFS / BFS: Connected Components & Reachability ⚑ Recursive DFS Traversal

Description

A company has n employees numbered 0 to n - 1. The manager array gives each employee's direct supervisor (manager[headID] = -1 for the head). The head initiates a chain of news spreading: they inform their direct reports, who each inform their own reports, and so on. Employee i takes informTime[i] minutes to notify all of their direct reports.

Return the total number of minutes until every employee has been informed.

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0]

Output: 0

Explanation: The head of the company is the only employee in the company.

Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]

Output: 1

Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.

The tree structure of the employees in the company is shown.

Code

1

2

3

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int: