LeetCode 1376. 通知所有员工所需的时间

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 旷视
标签
深度优先搜索 树 广度优先搜索

题目描述

✅ 1376. 通知所有员工所需的时间

image-20260929082522818

image-20260929082522968

题意分析

员工的管理关系是一棵以 headID 为根的树。负责人在时刻零已经知道消息，员工收到消息后，再用自己的 informTime 分钟通知全部直属下属。

同一上级的直属下属在这段时间后一起收到消息，各分支随后并行向下传播。要求的是最后一名员工收到消息的时刻，不是所有人的通知时间总和，也不是管理树的层数。

解法：树上 BFS 传播收到时刻

核心思路

[!blue]

输入 manager[i] 给出了员工的上级，而传播需要从上级找到下属，因此先反向建立每个员工的直属下属列表。负责人对应的上级为 -1，这一项不作为普通下标使用。

队列状态保存员工编号和他收到消息的时刻 receiveTime。如果当前员工在时刻 t 收到消息，那么他的每个直属下属都会在 t + informTime[employee] 收到；这里增加的是发出通知的上级所需时间，不是下属自己的时间。

管理关系是树，每个员工从负责人出发的路径唯一。因此收到时刻就是这条路径上各祖先通知时间的总和，沿树传递一次就能得到准确结果，无需在多条路线间比较，也无需反复更新同一员工。

队列用于遍历管理树，并不保证按收到时刻排序，因为不同上级的通知时间可能不同。每取出一个状态就更新最大收到时刻，直到全部员工处理完；所有人并行传播，所以全局完成时间取各路径到达时刻的最大值。

最末层员工已经收到消息就满足目标，不需要再加上他们自己的后续通知时间。公司只有负责人时，初始时刻零自然就是答案。

解题步骤

  1. 为每名员工准备下属列表，遍历 manager，将非负责人加入其上级的列表。
  2. 把负责人状态 (headID, 0) 放入队列，初始化答案为零。
  3. 取出员工和收到时刻，更新全局最大值。
  4. 将每个直属下属连同 receiveTime + informTime[employee] 加入队列。
  5. 所有状态处理完成后，返回最晚收到消息的时刻。

代码实现

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        // 按上级建立下属表，便于自顶向下传播。
        List<List<Integer>> g = new ArrayList<>(n);

        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            int m = manager[i];

            if (m != -1) {
                g.get(m).add(i);
            }
        }

        Queue<int[]> queue = new ArrayDeque<>();

        // 负责人在时刻零已经收到消息，起点不一定是编号零。
        queue.offer(new int[] {
            headID,
            0
        });
        int answer = 0;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int employee = cur[0];
            int receiveTime = cur[1];

            // 分支并行，只取最晚收到消息的时刻。
            answer = Math.max(answer, receiveTime);

            // 下属收到时刻加的是当前上级的通知时间。
            for (int subordinate : g.get(employee)) {
                queue.offer(new int[] {
                    subordinate,
                    receiveTime + informTime[employee]
                });
            }
        }

        return answer;
    }
}

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    // 按上级建立直属下属列表，便于自顶向下传播。
    g := make([][]int, n)
    for i := range manager {
        if manager[i] != -1 {
            g[manager[i]] = append(g[manager[i]], i)
        }
    }

    type state struct {
        employee, receiveTime int
    }
    // 负责人在时刻零已经收到消息，起点不一定是编号零。
    queue := []state{
        {headID, 0},
    }
    answer := 0
    for head := 0; head < len(queue); head++ {
        cur := queue[head]
        // 分支并行，只取最晚收到消息的时刻。
        if cur.receiveTime > answer {
            answer = cur.receiveTime
        }
        // 下属收到时刻加的是当前上级的通知时间。
        for _, subordinate := range g[cur.employee] {
            queue = append(queue, state{
                subordinate,
                cur.receiveTime + informTime[cur.employee],
            })
        }
    }
    return answer
}

复杂度分析

设员工数为 $n$。

  • 时间复杂度：$O(n)$，建立下属表和传播消息都只处理每名员工、每条管理边一次。
  • 辅助空间复杂度：$O(n)$，下属表和队列状态总规模均为线性；Go 的队列保留已经读取的前缀，也被该上界包含。

关键点总结

[!green]

  • 状态记录收到消息的时刻，向下传递时增加当前上级的通知时间。
  • 唯一管理路径上的耗时相加，不同分支并行，因此全局取最大值。
  • BFS 在这里负责遍历，不依赖队列按时间递增。

易错点总结

[!yellow]

  • 传递给下属时加 informTime[subordinate]，会把耗时算到错误的节点上。
  • 从编号零开始可能选错根，必须使用给定的 headID。
  • 同一上级有多个下属，不代表其通知时间要乘以下属人数，他们在同一时刻收到消息。
  • 用层数代替时间会忽略不同管理边的耗时差异。
  • 建下属表时要跳过 manager[headID] == -1，不能把它当作数组下标。

相似题目

题目 难度 关联与区别
690. 员工的重要性 中等 同样按员工树递归，本题取到各下属的最大传播时间，不能像重要度那样把所有分支时间直接相加。
743. 网络延迟时间 中等 最终都取最晚到达时间，本题组织结构是树且路径唯一，可直接沿树累计而不必做一般图最短路。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/57463229
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！