← Static tasks

1376. Time Needed to Inform All Employees

leetcode medium

#array#csharp#graph#leetcode#math#medium#tree

Task

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости.

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости.

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]

Output: 1

Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.

The tree structure of the employees in the company is shown.

C# solution

matched/original
public class Solution {
    private int maxTime = int.MinValue;
    
    private void DFS(List<int>[] adjList, int[] informTime, int curr, int time) {
        maxTime = Math.Max(maxTime, time);
        foreach (int adjacent in adjList[curr]) {
            DFS(adjList, informTime, adjacent, time + informTime[curr]);
        }
    }
    
    public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        List<int>[] adjList = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new List<int>();
        }
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                adjList[manager[i]].Add(i);
            }
        }
        DFS(adjList, informTime, headID, 0);
        return maxTime;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int maxTime = int.MinValue;
    
    private void DFS(List<int>[] adjList, vector<int>& informTime, int curr, int time) {
        maxTime = max(maxTime, time);
        foreach (int adjacent in adjList[curr]) {
            DFS(adjList, informTime, adjacent, time + informTime[curr]);
        }
    }
    
    public int NumOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        List<int>[] adjList = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new List<int>();
        }
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                adjList[manager[i]].push_back(i);
            }
        }
        DFS(adjList, informTime, headID, 0);
        return maxTime;
    }
}

Java solution

matched/original
class Solution {
    private int maxTime = Integer.MIN_VALUE;
    
    private void DFS(List<Integer>[] adjList, int[] informTime, int curr, int time) {
        maxTime = Math.max(maxTime, time);
        for (int adjacent : adjList[curr]) {
            DFS(adjList, informTime, adjacent, time + informTime[curr]);
        }
    }
    
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        List<Integer>[] adjList = new List[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                adjList[manager[i]].add(i);
            }
        }
        DFS(adjList, informTime, headID, 0);
        return maxTime;
    }
}

JavaScript solution

matched/original
class Solution {
    constructor() {
        this.maxTime = -Infinity;
    }
    
    DFS(adjList, informTime, curr, time) {
        this.maxTime = Math.max(this.maxTime, time);
        for (const adjacent of adjList[curr]) {
            this.DFS(adjList, informTime, adjacent, time + informTime[curr]);
        }
    }
    
    numOfMinutes(n, headID, manager, informTime) {
        const adjList = Array.from({ length: n }, () => []);
        for (let i = 0; i < n; i++) {
            if (manager[i] !== -1) {
                adjList[manager[i]].push(i);
            }
        }
        this.DFS(adjList, informTime, headID, 0);
        return this.maxTime;
    }
}

Python solution

matched/original
class Solution:
    def __init__(self):
        self.maxTime = float('-inf')
    
    def DFS(self, adjList, informTime, curr, time):
        self.maxTime = max(self.maxTime, time)
        for adjacent in adjList[curr]:
            self.DFS(adjList, informTime, adjacent, time + informTime[curr])
    
    def numOfMinutes(self, n, headID, manager, informTime):
        adjList = [[] for _ in range(n)]
        for i in range(n):
            if manager[i] != -1:
                adjList[manager[i]].append(i)
        self.DFS(adjList, informTime, headID, 0)
        return self.maxTime

Go solution

matched/original
type Solution struct {
    maxTime int
}

func (s *Solution) DFS(adjList [][]int, informTime []int, curr int, time int) {
    if time > s.maxTime {
        s.maxTime = time
    }
    for _, adjacent := range adjList[curr] {
        s.DFS(adjList, informTime, adjacent, time + informTime[curr])
    }
}

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    adjList := make([][]int, n)
    for i := 0; i < n; i++ {
        if manager[i] != -1 {
            adjList[manager[i]] = append(adjList[manager[i]], i)
        }
    }
    s := &Solution{maxTime: int(^uint(0) >> 1)}
    s.DFS(adjList, informTime, headID, 0)
    return s.maxTime
}

Explanation

Algorithm

Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎