We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Time Needed to Inform All Employees

Difficulty: Medium

Problem Description

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID. Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news. The i-th employee needs informTime[i] minutes to inform all of his direct subordinates. Return the number of minutes needed to inform all the employees about the urgent news.

Key Insights

  • The company structure is a tree where each manager informs their direct subordinates.
  • The problem can be solved using Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the tree.
  • The time taken to inform all employees is dependent on the maximum time taken by any employee to inform their subordinates.

Space and Time Complexity

Time Complexity: O(n) - We need to visit each employee once. Space Complexity: O(n) - The space complexity is mainly due to the recursion stack or the queue used for the traversal.

Solution

To solve the problem, we can represent the company's hierarchy as a tree using an adjacency list. Each employee can be a node, and each manager-subordinate relationship can be represented as edges. We will use either a Depth-First Search (DFS) or Breadth-First Search (BFS) approach to calculate the total time needed to inform all employees.

  1. Build an adjacency list where each manager points to their direct subordinates.
  2. Start from the head of the company and recursively (or iteratively) calculate the time required for each employee to inform their subordinates.
  3. Keep track of the maximum time taken across all paths in the tree.

Code Solutions

def numOfMinutes(n, headID, manager, informTime):
    from collections import defaultdict
    
    # Create an adjacency list for the employees
    graph = defaultdict(list)
    for emp in range(n):
        if manager[emp] != -1:
            graph[manager[emp]].append(emp)
    
    # DFS function to calculate the time needed
    def dfs(emp):
        total_time = 0
        for subordinate in graph[emp]:
            total_time = max(total_time, dfs(subordinate))
        return total_time + informTime[emp]
    
    # Start DFS from the head of the company
    return dfs(headID)
← Back to All Questions