Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Time Needed to Inform All Employees (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

A company has n employees, each with a unique ID from 0 to n-1. The head of the company has an ID headID.

Each employee has a direct manager, indicated by the manager array, where manager[i] is the direct manager of the i<sup>th</sup> employee. The head of the company has no manager, so manager[headID] = -1.

The company needs to inform all employees about urgent news. The head will inform their direct subordinates, who will then inform their subordinates, and so on. Each employee i needs informTime[i] minutes to inform all their direct subordinates.

Return the number of minutes needed to inform all the employees about the urgent news.

Examples

Example 1

  • Input: n: 6, headID: 2, manager: [2, 2, -1, 2, 2, 2], informTime: [0, 0, 1, 0, 0, 0]
Image
  • Output: 1
  • Explanation: Employee 2 informs all subordinates (0, 1, 3, 4, 5) in 1 minute.

Example 2

  • Input: n: 4, headID: 0, manager: [-1, 0, 0, 1], informTime: [2, 1, 0, 0]
Image
  • Output: 3
  • Explanation:
    • Employee 0 informs 1 and 2 in 2 minutes.
    • Employee 1 informs 3 in 1 more minute. Total time = 2 + 1 = 3 minutes.

Example 3

  • Input: n: 7, headID: 6, manager: [1, 3, 3, 4, 6, 6, -1], informTime: [0, 2, 0, 1, 2, 0, 1]
  • Output: 6
  • Explanation: Employee 6 informs 4 and 5 in 1 minute, 4 informs 3 in 2 minute, 3 informs 1 and 2 in 1 minute,and 1 informs 0 in 2 minutes. Total time = 1 + 2 + 1 + 2 = 6 minutes.

Constraints:

  • 1 <= n <= 10<sup>5</sup>
  • 0 <= headID < n
  • manager.length == n
  • 0 <= manager[i] < n
  • manager[headID] == -1
  • informTime.length == n
  • 0 <= informTime[i] <= 1000
  • informTime[i] == 0 if employee i has no subordinates.
  • It is guaranteed that all the employees can be informed.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible