通知所有员工所需的时间

标签: 树 深度优先搜索 广度优先搜索

难度: Medium

公司里有 n 名员工，每个员工的 ID 都是独一无二的，编号从 0 到 n - 1。公司的总负责人通过 headID 进行标识。

在 manager 数组中，每个员工都有一个直属负责人，其中 manager[i] 是第 i 名员工的直属负责人。对于总负责人，manager[headID] = -1。题目保证从属关系可以用树结构显示。

公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。

第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属（也就是说在 informTime[i] 分钟后，他的所有直属下属都可以开始传播这一消息）。

返回通知所有员工这一紧急消息所需要的 分钟数 。

示例 1：

输入：n = 1, headID = 0, manager = [-1], informTime = [0]
输出：0
解释：公司总负责人是该公司的唯一一名员工。

示例 2：

输入：n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
输出：1
解释：id = 2 的员工是公司的总负责人，也是其他所有员工的直属负责人，他需要 1 分钟来通知所有员工。
上图显示了公司员工的树结构。

提示：

  • 1 <= n <= 10^5
  • 0 <= headID < n
  • manager.length == n
  • 0 <= manager[i] < n
  • manager[headID] == -1
  • informTime.length == n
  • 0 <= informTime[i] <= 1000
  • 如果员工 i 没有下属，informTime[i] == 0 。
  • 题目 保证 所有员工都可以收到通知。

Submission

运行时间: 148 ms

内存: 27.4 MB

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

        for idx, manag in enumerate(manager):
            if manag >= 0:
                m[manag].append(idx)

        def dfs(x):
            maxTime = 0

            for sub in m[x]:
                maxTime = max(maxTime, dfs(sub))
            return maxTime + informTime[x]
        return dfs(headID)

Explain

此题解利用深度优先搜索(DFS)来遍历员工的层级结构，并计算通知到每个员工所需的最长时间。首先，通过一个字典`m`构建一个从上司到直属下属的映射关系，然后使用递归的DFS方法来遍历这个从属树结构。对于每个员工`x`，递归地计算通知到其所有下属所需的最长时间，然后将这个时间加上`x`自己传递信息所需的时间`informTime[x]`，从而得到总时间。最终，从总负责人（即`headID`）开始调用这个DFS函数，得到结果。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        m = defaultdict(list)  # 创建从上司到下属的映射关系

        for idx, manag in enumerate(manager):
            if manag >= 0:
                m[manag].append(idx)  # 填充映射关系

        def dfs(x):
            maxTime = 0  # 初始化最长通知时间

            for sub in m[x]:
                maxTime = max(maxTime, dfs(sub))  # 递归计算下属的最长通知时间，并更新当前最大值
            return maxTime + informTime[x]  # 返回当前员工的总通知时间（包括自己的通知时间）
        return dfs(headID)  # 从总负责人开始计算通知时间

Explore

在构建从上司到下属的映射关系时，选择使用字典（散列表）主要是因为字典提供了快速的查找、插入和删除操作。在此场景中，每个上司可能有多个直接下属，使用字典可以快速地通过上司的ID直接访问所有直接下属的列表。如果使用数组或链表，虽然可以实现相同的功能，但在查找和更新上司与下属的关系时可能需要更多时间，特别是当上司的数量很多或者下属关系频繁变动时。字典通过键-值对的方式，能够直接映射每个上司ID到其下属列表，使得数据的管理更为高效。

在递归的DFS方法中，确保不会出现循环引用或重复访问的关键在于题目条件和递归结构的设计。题目已确保从属关系可以用树结构表示，这意味着每个节点（员工）只有一个上司，并且不存在循环从属关系（如A是B的上司，同时B是A的上司的情况）。由于树结构的这一特性，从任一节点开始的DFS不会回到已访问的节点，因此在遍历过程中不会有重复访问或循环引用的问题。此外，递归DFS在设计时通常只访问未被访问的节点，确保每个节点只被处理一次。

是的，DFS函数中maxTime初始化为0确实意味着对于没有下属的员工（叶子节点），其通知时间完全由informTime[x]决定。这是因为叶子节点没有下属，所以递归调用返回的最长通知时间为0，因此该员工的总通知时间就是其自身传递信息所需的时间informTime[x]。这种设计有效地处理了从属树结构中的叶节点情况，确保计算结果的正确性。