1376. Time Needed to Inform All Employees - Medium

前往題目

想法

• DFS找最長路徑

思路

1. BFS
2. 先建立manager -> employees的map
3. 然後就是一般的BFS，每個employee都要加上其manager的時間，這樣才是通知到那位employee的完整時間
4. 每次到新的僱員時更新結果

Code

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        // Manager -> employees
        HashMap<Integer, ArrayList<Integer>> map = new HashMap();

        // Build the relationships
        for (int i = 0; i < n; ++i) {
            // Get the list or create a new one
            ArrayList<Integer> list = map.getOrDefault(manager[i], new ArrayList<>());
            list.add(i); // Add the element to the list
            map.put(manager[i], list); // Put the updated list back in the map
        }

        int res = 0;
        
        // Queue of "id, time"
        Queue<Pair<Integer, Integer>> q = new LinkedList();
        // Add the CEO
        q.offer(new Pair(headID, informTime[headID]));

        while (!q.isEmpty()) {
            int size = q.size();
            int id = q.peek().getKey();
            int time = q.poll().getValue();

            // Update the result
            res = Math.max(res, time);

            if (map.containsKey(id)) {
                // Add the employees of the current manager
                for (int emp : map.get(id)) {
                    q.offer(new Pair(emp, time + informTime[emp]));
                }
            }
        }
        return res;
    }
}