diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/inform_employees.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/inform_employees.cpp')
-rw-r--r-- | other/inform_employees.cpp | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/other/inform_employees.cpp b/other/inform_employees.cpp new file mode 100644 index 0000000..700ccc3 --- /dev/null +++ b/other/inform_employees.cpp @@ -0,0 +1,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 +} |