Last Updated: 29 Dec, 2021
Inform Employees
Hard
Asked in companies
You are in a company with ‘N’ employees each with a unique ID from ‘0 to N - 1’. You are given a list of managers, where ‘manager[i]’ is the direct manager of ‘ith’ employee. You are also given an array ‘timeToInform’ where ‘timeToInform[i]’ is the time it takes for ‘ith’ employee to send information to all his subordinates. Your task is to find out how much time it will take for any piece of information to reach all employees. You are also given ‘headId’ that is the ID of the head of the company.
For example:
You are given ‘manager’ = [-1, 0, 0, 1, 1], ‘timeToInform’ = [1, 1, 0, 0, 0], ‘headId’ = [0],
We can see employee ‘0’ will take 1 time to inform their subordinates, that are employee 1, and employee 2, and employee 1 will take 1 time to inform their subordinates that are employee 3 and employee 4. The total time taken is 2. Hence the answer is 2.
Input Format:
The first line of input contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘headId’ representing the number of employees and the employee id of the head of the company.
The second line of each test case contains ‘N’ space-separated integers representing the elements of the ‘manager’ array.
The third line of each test case contains ‘N’ space-separated integers representing the ‘timeToInform’ array.
Output Format:
For each test case, print a single integer representing the time it takes to inform all the employees
Print a separate line for each test case.
Constraints
1 <= T <= 10
1 <= N <= 10^5
0 <= headId, manager[i] < N
0 <= timeToInform[i] <= 10^4
manager[headId] = -1
Time Limit = 1 sec
Approaches
In this approach, we can create a tree out of the given information and traverse it. For any node, the time taken is the maximum time taken by its subordinates and the timeToInform of that node.
We will create a dfs(employeeId, subordinates, timeToInform), where employeeId is the id of the employee we are currently looking, ‘subordinates’ is the map containing the list of all subordinates of any employee, and ‘timeToInform is the array given in the problem.
Algorithm:
- In the dfs(employeeId, subordinates, timeToInform)
- Set maximumTime as 0
- Iterate sub through subordinates[employeeId]
- Set maximumTime as maximum of itself and dfs(sub, subordinates, timeToinform) + timeToInform[employeeId]
- Return maximumTime
- In the given function
- Initialise an empty hash map of integers and key and array as values, ‘subordinates’
- Iterate over all the indices of manager and set m as manager[index]
- If index is not equal to headId, insert index into subordinates[m]
- Return dfs(headId, subordinates, timeToInform)
In this approach, we will traverse the graph, but since we are doing it in a breadth-first search, we will have to maintain an array ‘empTime’ which will keep track of overall time taken by an employee, for each employee we will add the overall time taken by their direct manager.
We will just return the maximum value in ‘empTime’.
Algorithm:
- Copy ‘timeToInform’ array into ‘empTime’
- Initialise an empty hash map of integers and key and array as values, ‘subordinates’
- Iterate over all the indices of manager and set m as manager[index]
- If index is not equal to headId, insert index into subordinates[m]
- Set maximumTime as 0
- Initialise an empty queue ‘queue’, insert headId into the ‘queue’
- While the length of the queue is not 0
- Deque the front of the queue and set it as ‘emp’
- Is manager[emp] does not equal to -1
- Add empTime[manager[empt]] to empTime[emp]
- Set maximumTime as the maximum of itself and empTime[emp]
- If subordinates[emp] is not NULL, insert all elements of the list subordinates[emp] into the queue
- Return maximumTime