Show problems as
Classic problem #1376MediumTreeDepth-First SearchBreadth-First Search

Time Needed to Inform All Employees

Real-world version: Relaying an Alert Down the Chain
Tracked in this browser only
Read Time Needed to Inform All Employees on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A brigade has count members numbered 0 through count - 1. The chain of command is given as an array: supervisor[i] is the number of the member who supervises member i, except that supervisor[lead] == -1 because the lead answers to nobody. Following the links upwards from any member always arrives at the lead, so the chain of command forms a tree rooted there.

When a member learns of an alert, they spend relayTime[i] minutes passing it on, after which all of the members they directly supervise know it at the same moment. A member who supervises nobody has relayTime[i] == 0.

The lead learns of the alert at minute 0. Return the number of minutes that pass before every member of the brigade knows.

Examples

Example 1

Input
count = 7, lead = 0, supervisor = [-1, 0, 0, 1, 1, 2, 2], relayTime = [1, 2, 5, 0, 0, 0, 0]
Output
6

Members 1 and 2 both hear the alert at minute 1. Members 3 and 4 hear it 2 minutes after that, at minute 3, and members 5 and 6 hear it 5 minutes after minute 1, at minute 6, by which point the whole brigade knows.

Example 2

Input
count = 4, lead = 0, supervisor = [-1, 0, 1, 2], relayTime = [3, 2, 1, 0]
Output
6

The chain runs 0 to 1 to 2 to 3, so member 1 hears it at minute 3, member 2 at minute 5 and member 3 at minute 6.

Example 3

Input
count = 5, lead = 3, supervisor = [3, 3, 3, -1, 3], relayTime = [0, 0, 0, 0, 0]
Output
0

The lead is member 3 and supervises the other four directly, spending no time on the relay, so everybody knows at minute 0.

Constraints

  • 1 <= count <= 10^5
  • 0 <= lead <= 10^5 - 1
  • supervisor.length == count
  • -1 <= supervisor[i] <= 10^5 - 1
  • relayTime.length == count
  • 0 <= relayTime[i] <= 1000
  • lead is a member number, and supervisor[lead] is -1 while every other entry of supervisor is a member number.
  • Following the supervisor links from any member reaches the lead.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def alert_minutes(count: int, lead: int, supervisor: list[int], relayTime: list[int]) -> int:
Java
public int alertMinutes(int count, int lead, int[] supervisor, int[] relayTime)

More on the same topics