Skip to content

3967. Finish Time of Tasks II πŸ”’

Description

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 an undirected tree. This is represented by a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected connection between task ui and task vi.

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

For any chosen task as the root, 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].
    • Finish time of task i is latest + ownDuration.

Choose any task as the root and compute the finish time of that root based on the rules above.

Return the minimum possible finish time among all choices of root.

Β 

Example 1:

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

Output: 14

Explanation:

0 9 1 1 2 5

The optimal choice is to treat task 1 as the root.

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

Thus, the minimum possible finish time among all choices of root is 14.

Example 2:

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

Output: 12

Explanation:

0 4 1 7 2 6

The optimal choice is to treat task 0 as the root.

  • 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

Thus, the minimum possible finish time among all choices of root is 12.

Example 3:

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

Output: 16

Explanation:

0 5 1 8 2 2 3 1

The optimal choice is to treat task 1 as the root.

  • 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 one child task 2:
    • earliest = latest = 3
    • ownDuration = (latest - earliest) + baseTime[0] = 0 + 5 = 5
    • Finish time of task 0 is latest + ownDuration = 3 + 5 = 8
  • Task 1 has one child task 0:
    • earliest = latest = 8
    • ownDuration = (latest - earliest) + baseTime[1] = 0 + 8 = 8
    • Finish time of task 1 is latest + ownDuration = 8 + 8 = 16

Thus, the minimum possible finish time among all choices of root is 16.

Β 

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 undirected tree.
  • baseTime.length == n
  • 1 <= baseTime[i] <= 105

Solutions

Solution 1

1


1


1


1

Comments