Время для оповещения всех сотрудников

 1376. Time Needed to Inform All Employees

В компании работают n сотрудников, каждый с уникальным ID от 0 до n - 1. У главы компании ID=headID.

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

Глава компании хочет известить всех сотрудников срочными новостями. Он передает новость своим прямым субординатам, а те - своим.И так далее, пока все сотрудники не получат эту новость.

Сотруднику с индексом i треубуется informTime[i] минут, чтобы известить своих субординатов. То есть после informTime[i] минут, все его субординаты начнут передавать новость дальше.

Вернуть число минут, которые нужны, чтобы известить всех сотрудников.

Пример 1:

Дано: n = 1, headID = 0, manager = [-1], informTime = [0]
Результат: 0
Пояснение: Глава компании - единственный сотрудник.

Пример 2:

Дано: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Результат: 1
Пояснение: Глава компании с id = 2 - непосредственный менеджер всех остальных сотрудников, и его informTime=1, то есть нужна 1 минута, чтобы оповестить всех сотрудников.
Структура компании показана в виде дерева на рисунке.
 

Ограничения:

• 1 <= n <= 105
• 0 <= headID < n
• manager.length == n
• 0 <= manager[i] < n
• manager[headID] == -1
• informTime.length == n
• 0 <= informTime[i] <= 1000
• informTime[i] == 0 если у сотрудника i нет субординатов.
•  Субординация гарантированно в виде дерева. И все сотрудники гарантированно могут быть оповещены.
  

Идея решения

Для любого сотрудника i мы можем пройтись по дереву, заданному массивом manager,  пока не дойдем до главы. У каждого сотрудника только 1 менджер, то есть время оповещения сотрудника - это сумма informTime тех индексов, которые расположены на пути от сотрудника до главы. Тогда ответ - это самая большая сумма на пути от главы до какого-либо листа дерева.

Мы рассматриваем каждый элемент i и считаем для него время оповещения, одновременно мы строим время оповещения для его менеджеров вплоть до главы. Тогда для другого сотрудника мы можем использовать ранее подситанное время оповещения его менеджеров.

То есть времяДо[i] = informTime[manager[i]]+времяДо[manager[i]], где времяДо[x] - это время от главы до x. Получается рекурсия.

Имплементация

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int[] minutes = new int[n]; // minutes[i] содержит количество минут, необходимых для оповещения сотрудника с индексом i     

        minutes[headID] = 1; // потом удалим эту 1
        int max = 1;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, find(manager, informTime, minutes, i));
        }
        return max - 1;
    }
    
    private int find(int[] parent, int[] time, int[] res, int n) {
        if (res[n] == 0) {
// если n-й сотрудник ещё не был подсчитан
//(поэтому был необходим minutes[headID] = 1, чтобы не зацикливаться)
            int p = parent[n];
            res[n] = find(parent, time, res, p) + time[p];
        }
        return res[n];
    }
}