Time Needed To Inform All Employees - Leetcode Solution

The problem statement is as follows:

You are given a list of employees who are informed of the latest news about the company. You are also given a number that represents the ID of the employee who broke the news. You need to calculate the total time it will take for all employees to be informed of the news.

Each employee must be informed of the news in the following manner:

1. The employee who broke the news will be informed immediately.
2. Each employee informed so far will inform their immediate subordinates in one unit of time.
3. The process repeats until all employees are informed.

You need to find the minimum number of units of time it will take for all employees to be informed.

To solve this problem, we can use a Breadth First Search (BFS) approach. We start by adding the ID of the employee who broke the news to a queue. We also create a dictionary to store the immediate subordinates of each employee.

We then loop through the queue while it is not empty. At each iteration, we remove the current employee from the queue and inform their immediate subordinates. We add these subordinates to the queue and increment the time it took to inform them.

We keep track of the maximum time it took to inform an employee. This will be the minimum time it takes to inform all employees.

Finally, we return the maximum time it took to inform an employee.

Here's the Python code that solves this problem:

def informTime(n, headID, manager, informTime):
    """
    :type n: int
    :type headID: int
    :type manager: List[int]
    :type informTime: List[int]
    :rtype: int
    """
    subordinates = {}
    for i, m in enumerate(manager):
        if m not in subordinates:
            subordinates[m] = []
        subordinates[m].append(i)
    
    queue = [(headID, 0)]
    max_time = 0
    
    while queue:
        current_employee, current_time = queue.pop(0)
        if current_employee in subordinates:
            for subordinate in subordinates[current_employee]:
                queue.append((subordinate, current_time + informTime[current_employee]))
        max_time = max(max_time, current_time)
    
    return max_time

The time complexity of this solution is O(n), where n is the number of employees, since we visit each employee only once. The space complexity is also O(n), since we store the immediate subordinates of each employee in a dictionary.

1