Mapping a Tree to a HashTable data structure II

Another problem where it gets easier if you map the tree to a HashTable. Keep in mind that this is an N-Ary tree, not binary. After that it is a straightforward pre-order depth-first-search (Pre-Order DPS). Code is down below, cheers, ACC.

Finish Time of Tasks I - LeetCode

You are given an integer n representing the number of tasks in a project, numbered from 0 to n - 1. These tasks are connected as a tree rooted at task 0. This is represented by a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that task ui is the parent of task vi.

You are also given an array baseTime of length n, where baseTime[i] represents the time to complete task i.

The finish time of each task is calculated as follows:

• Leaf task: The finish time is baseTime[i].
• Non-leaf task:
  • Let earliest be the minimum finish time among its children, and latest be the maximum finish time among its children.
  • Let ownDuration be (latest - earliest) + baseTime[i].
  • The finish time of task i is latest + ownDuration.

Return the finish time of the root task 0.

 

Example 1:

Input: n = 3, edges = [[0,1],[1,2]], baseTime = [9,5,3]

Output: 17

Explanation:

• Task 2 is a leaf, so its finish time is baseTime[2] = 3.
• Task 1 has one child task 2:
  • earliest = latest = 3
  • ownDuration = (latest - earliest) + baseTime[1] = 5
  • Finish time of task 1 is 3 + 5 = 8
• Task 0 has one child with finish time 8:
  • earliest = latest = 8
  • ownDuration = (latest - earliest) + baseTime[0] = 9
  • Finish time of task 0 is 8 + 9 = 17

Example 2:

Input: n = 3, edges = [[0,1],[0,2]], baseTime = [4,7,6]

Output: 12

Explanation:

• Task 1 is a leaf, so its finish time is baseTime[1] = 7.
• Task 2 is a leaf, so its finish time is baseTime[2] = 6.
• Task 0 has two children with finish times 7 and 6:
  • earliest = 6, latest = 7
  • ownDuration = (latest - earliest) + baseTime[0] = (7 - 6) + 4 = 5
  • Finish time of task 0 is latest + ownDuration = 7 + 5 = 12

Example 3:

Input: n = 4, edges = [[0,1],[0,2],[2,3]], baseTime = [5,8,2,1]

Output: 18

Explanation:

• Task 1 is a leaf, so its finish time is baseTime[1] = 8.
• Task 3 is a leaf, so its finish time is baseTime[3] = 1.
• Task 2 has one child task 3:
  • earliest = latest = 1
  • ownDuration = (latest - earliest) + baseTime[2] = 0 + 2 = 2
  • Finish time of task 2 is latest + ownDuration = 1 + 2 = 3
• Task 0 has two children with finish times 8 and 3:
  • earliest = 3, latest = 8
  • ownDuration = (latest - earliest) + baseTime[0] = (8 - 3) + 5 = 10
  • Finish time of task 0 is latest + ownDuration = 8 + 10 = 18

 

Constraints:

• 1 <= n <= 105
• edges.length = n - 1
• edges[i] == [ui, vi]
• 0 <= ui, vi <= n - 1
• ui != vi
• The input is generated such that edges represents a valid tree.
• baseTime.length == n
• 1 <= baseTime[i] <= 105​​​​​​​

public class Solution {
    public long FinishTime(int n, int[][] edges, int[] baseTime)
    {
        Hashtable tree = new Hashtable();

        foreach (int[] edge in edges)
        {
            int parent = edge[0];
            int child = edge[1];

            if (!tree.ContainsKey(parent)) tree.Add(parent, new HashSet());
            HashSet children = (HashSet)tree[edge[0]];
            if (!children.Contains(child)) children.Add(child);
        }

        return _FinishTime(tree, 0, baseTime);
    }

    private long _FinishTime(Hashtable tree, int currentIndex, int[] baseTime)
    {
        //Leaf cases
        if (!tree.ContainsKey(currentIndex)) 
            return (long)baseTime[currentIndex];

        HashSet children = (HashSet)tree[currentIndex];
        if (children.Count == 0)
            return (long)baseTime[currentIndex];

        //Non-leaf cases
        long earliestTime = Int64.MaxValue;
        long latestTime = Int64.MinValue;
        foreach (int child in children)
        {
            long childFinishTime = _FinishTime(tree, child, baseTime);
            earliestTime = Math.Min(earliestTime, childFinishTime);
            latestTime = Math.Max(latestTime, childFinishTime);
        }

        long ownDuration = (latestTime - earliestTime) + baseTime[currentIndex];

        return latestTime + ownDuration;
    }
}