DIY: Time Needed to Inform All Employees

Problem statement

A company has n employees, and each employee has a unique ID from 0 to n - 1. The ID of the head of the company is headID.

Each employee has one direct manager given in the manager array. In the manager array, manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Subordinate relationships are also guaranteed to have a tree structure.

The head of the company wants to inform all the company’s employees of an urgent piece of news. The head of the company will inform their direct subordinates, who will inform their subordinates and so on, until all of the employees know the news. Any employee can only relay the message to their immediate subordinates only.

The i-th employee needs informTime[i] minutes to inform all of their direct subordinates (After informTime[i] minutes, all of their direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

Input

The following is an example input:

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

      2
  / / | \ \
 0 1  3  4 5

Output

The following is an example output:

1

The company head (with id = 2) is the only manager of all the employees and needs 1 minute to inform all of them.

Coding exercise

For this coding exercise, you need to implement the numOfMinutes(n, headID, manager, informTime) function, where n is the number of employees, headID represents the company’s head, manager is the list of managers, and informTime is the time required by employees to convey the message. The function should return the number of minutes needed to inform all the employees.