LeetCode in Kotlin

3965. Finish Time of Tasks I

Medium

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
• The finish time of every task is guaranteed to be less than 253.

Solution

class Solution {
    fun finishTime(n: Int, edges: Array<IntArray>, baseTime: IntArray): Long {
        val torqavemi = edges
        val outDegree = IntArray(n)
        val parent = IntArray(n)
        for (i in 0..<n) {
            parent[i] = -1
        }
        for (edge in torqavemi) {
            val u = edge[0]
            val v = edge[1]
            parent[v] = u
            outDegree[u]++
        }
        val earliest = LongArray(n)
        val latest = LongArray(n)
        for (i in 0..<n) {
            earliest[i] = Long.MAX_VALUE
            latest[i] = Long.MIN_VALUE
        }
        val finish = LongArray(n)
        val queue = IntArray(n)
        var head = 0
        var tail = 0
        for (i in 0..<n) {
            if (outDegree[i] == 0) {
                queue[tail++] = i
            }
        }
        while (head < tail) {
            val u = queue[head++]
            if (earliest[u] == Long.MAX_VALUE) {
                finish[u] = baseTime[u].toLong()
            } else {
                finish[u] = 2 * latest[u] - earliest[u] + baseTime[u]
            }
            val p = parent[u]
            if (p != -1) {
                if (finish[u] < earliest[p]) {
                    earliest[p] = finish[u]
                }
                if (finish[u] > latest[p]) {
                    latest[p] = finish[u]
                }
                outDegree[p]--
                if (outDegree[p] == 0) {
                    queue[tail++] = p
                }
            }
        }
        return finish[0]
    }
}

This site is open source. Improve this page.