24. Time Needed to Inform All Employees

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.

Example 2:

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.

Example 3:

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
Output: 21
Explanation: The head has id = 6. He will inform employee with id = 5 in 1 minute.
The employee with id = 5 will inform the employee with id = 4 in 2 minutes.
The employee with id = 4 will inform the employee with id = 3 in 3 minutes.
The employee with id = 3 will inform the employee with id = 2 in 4 minutes.
The employee with id = 2 will inform the employee with id = 1 in 5 minutes.
The employee with id = 1 will inform the employee with id = 0 in 6 minutes.
Needed time = 1 + 2 + 3 + 4 + 5 + 6 = 21.

Example 4:

Input: n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]
Output: 3
Explanation: The first minute the head will inform employees 1 and 2.
The second minute they will inform employees 3, 4, 5 and 6.
The third minute they will inform the rest of employees.

Example 5:

Input: n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914]
Output: 1076

Solution: (DFS)

As it is a tree structure no need of visited array Edge Case:-

                            ---> 1(213) -> 7(0)
                           /
4(686)->10(337)->3(253)->9(309)->6(975) -> 2(0)
                           \
                            ---> 8(261) -> 5(170) -> 0(0)
                            
wrong: 686+337+253+309+975+170 = 2730
correct: 686+337+253+309+975 = 2560

Performing bfs and fidning max of all level gives error
975 > (261 + 170), 8(261) -> 5(170)

class Solution
{
public:
    int dfs(vector<int> v[], int node, vector<int> &ift, int time)
    {

        int totalTime = time;
        for (int i = 0; i < v[node].size(); i++)
        {
            int temp = dfs(v, v[node][i], ift, time + ift[v[node][i]]);
            totalTime = max(totalTime, temp);
        }
        return totalTime;
    }

    int numOfMinutes(int n, int headID, vector<int> &manager, vector<int> &informTime)
    {
        vector<int> v[n];

        for (int i = 0; i < manager.size(); i++)
        {
            if (i != headID)
            {
                v[manager[i]].push_back(i);
            }
        }

        int time = dfs(v, headID, informTime, informTime[headID]);
        return time;
    }
};