aboutsummaryrefslogtreecommitdiff
path: root/inform_employees.cpp
blob: 700ccc3169cc98382cdc005f1910ed9ef5a8d722 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 1376. Time Needed to Inform All Employees
#include "leetcode.h"

/*
 * a company has 'n' employees with a unique id for each employee from 0 to 'n -
 * 1'. the head of the company is the one with the 'head_id'. each employee has
 * one direct manager given the 'manager' array where 'manager[i]' is the direct
 * manager of the i'th employee, 'manager[head_id] = -1'. also it is guaranteed
 * that the subordination relations have a tree structure. the head of the
 * company wants to inform all the company employees of an urgent piece of new.
 * he will inform his direct subordinates, and they will inform their
 * subordinates and so on until all the employees know about the urgent news.
 * the i'th employee needs 'inform_time[i]' minutes to inform all of his direct
 * subordinates (ie. after 'inform_time[i]' minutes, all his direct subordinates
 * can start spreading the news) return the number of minutes needed to inform
 * all the employees about the urget news.
 */

class Solution {
  int dfs(int i, vector<int> &manager, vector<int> &inform_time) {
    if (manager[i] != -1) {
      inform_time[i] += dfs(manager[i], manager, inform_time);
      manager[i] = -1;
    }
    return inform_time[i];
  }

public:
  int numOfMinutes(int n, int head_id, vector<int> &manager,
                   vector<int> &inform_time) {
    int ans = 0;
    for (int i = 0; i < n; ++i)
      ans = max(ans, dfs(i, manager, inform_time));
    return ans;
  }
};

int main() {
  Solution obj;
  vector<int> m1 = {-1}, m2 = {2, 2, -1, 2, 2, 2};
  vector<int> it1 = {0}, it2 = {0, 0, 1, 0, 0, 0};
  printf("%d\n", obj.numOfMinutes(1, 0, m1, it1)); // expect: 0
  printf("%d\n", obj.numOfMinutes(6, 2, m2, it2)); // expect: 1
}