Message Broadcast Time in an Org Tree
Problem statement
A company has n employees numbered 0 to n - 1. Employee 0 is the CEO, and parent[i] is the manager of employee i (parent[0] = -1).
At time 0 the CEO has a message. A manager can only pass it to their own direct reports, and passing it to one report takes 1 unit of time. Find the earliest time by which every employee has the message, in two settings:
- Parallel: a manager tells all of their direct reports at the same moment, 1 unit after they themselves heard it.
- One at a time: a manager tells one direct report per unit of time, in any order they choose: the first report hears 1 unit after the manager did, the second 2 units after, and so on. Every manager picks the order that makes the final time as small as possible.
Return [parallelTime, oneAtATimeTime]. With only the CEO, both are 0.
Function
broadcastTimes(parent: int[]) → int[]Examples
Example 1
parent = [-1,0,0,1,1,1]return = [2,4]In parallel, employees 1 and 2 hear at time 1 and employees 3, 4 and 5 at time 2, so everyone knows by time 2. One at a time, the CEO should tell employee 1 first (time 1), because employee 1 still has three people to tell; they hear at times 2, 3 and 4. Employee 2 hears from the CEO at time 2. Everyone knows by time 4.
Example 2
parent = [-1]return = [0,0]The CEO is the only employee, so no message needs to be passed: both times are 0.
Example 3
parent = [-1,0,1]return = [2,2]A chain: each person has one report, so the order does not matter and both times are 2.
Constraints
1 <= parent.length <= 800parent[0] == -1, and0 <= parent[i] < parent.lengthfor everyi >= 1- The reporting lines form one tree with employee
0at the top (no cycles).