Minimum Notification Time (Tree Broadcast)

# Minimum Notification Time (Tree Broadcast) ## Difficulty Medium ## Tags `tree`, `greedy`, `dfs` ## Problem Statement A general needs to notify all soldiers in a military hierarchy. The hierarchy is represented as a tree where the general is the root. **Rules:** - Each person can only call **one subordinate at a time**. - Each call takes **1 unit of time**. - After calling, the caller can immediately call another subordinate. - The subordinate can start calling their own subordinates as soon as they receive the call. Find the **minimum time** required for everyone to receive the notification. ## Constraints - The tree has N nodes (1 ≤ N ≤ 10⁴). - The tree is represented as an adjacency list where `children[i]` is the list of direct subordinates of node `i`. - Root is node 0. ## Signatures ### Python ```python def min_notification_time(children: Dict[int) -> int: pass ``` ### Java ```java public class Solution { public int min_notification_time(Object children) { return null; } } ``` ### Csharp ```csharp public class Solution { public int min_notification_time(Object children) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int min_notification_time(Object children) { } }; ``` ### C ```c int min_notification_time(Object children) { } ``` ### Ruby ```ruby def min_notification_time(children) end ``` ### Perl ```perl sub min_notification_time { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def min_notification_time(children: Object): Int = { } } ``` ### Haskell ```haskell min_notification_time :: ... -> ... min_notification_time args = undefined ``` ### Clojure ```clojure (defn min_notification_time [children] ) ``` ### Scheme ```scheme (define (min_notification_time children) ) ``` ## Examples ### Example 1 **Input:** ``` children = {0: [1, 2], 1: [], 2: []} ``` **Output:** ``` 2 ``` **Explanation:** - t=1: General calls node 1 (or 2) - t=2: General calls node 2 (or 1) - Total: 2 time units ### Example 2 **Input:** ``` children = {0: [1, 2], 1: [3, 4], 2: []} ``` **Output:** ``` 3 ``` **Explanation:** - t=1: General calls node 1 - t=2: General calls node 2. Simultaneously, node 1 calls node 3. - t=3: Node 1 calls node 4. - Total: 3 time units ### Example 3 **Input:** ``` children = {0: [1], 1: [2], 2: [3], 3: []} ``` **Output:** ``` 3 ``` **Explanation:** Linear chain of 4 people. General → 1 → 2 → 3. Takes 3 calls. ### Example 4 **Input:** ``` children = {0: [1, 2, 3], 1: [], 2: [], 3: []} ``` **Output:** ``` 3 ``` **Explanation:** General must make 3 sequential calls. ### Example 5 **Input:** ``` children = {0: [1, 2], 1: [3, 4, 5], 2: [6]} ``` **Output:** ``` 4 ``` **Explanation:** - Optimal: General calls 1 first (subtree needs more time), then 2. - t=1: General→1 - t=2: General→2, 1→child (longest subtree first) - Continue optimally... ## Hints 1. Use **post-order DFS** to calculate the time needed for each subtree. 2. **Greedy insight**: Call the child with the longest subtree time first. 3. For a node with children needing times [t1, t2, t3, ...]: - Sort in descending order. - If called in order, child i (0-indexed) starts at time i+1. - Total time = max(t_i + i + 1) for all children. 4. Leaf nodes have time = 0.