Skip to content

3965. Finish Time of Tasks I

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 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:

0 9 1 5 2 3
  • 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:

0 4 1 7 2 6
  • 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.

Solutions

Solution 1: DFS

First, build the tree from the edge list \(\textit{edges}\) and store each node's children in an adjacency list \(g\).

Then perform DFS starting from the root node \(0\). Define a function \(\textit{dfs}(i)\) that returns the finish time of task \(i\):

  • If \(i\) is a leaf node, return \(\textit{baseTime}[i]\) directly;
  • Otherwise, recursively compute the finish times of all children, and let \(\textit{earliest}\) and \(\textit{latest}\) be the minimum and maximum among them;
  • The own duration of the current task is \(\textit{ownDuration} = (\textit{latest} - \textit{earliest}) + \textit{baseTime}[i]\);
  • The finish time of task \(i\) is \(\textit{latest} + \textit{ownDuration}\).

The answer is \(\textit{dfs}(0)\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the number of nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def finishTime(self, n: int, edges: List[List[int]], baseTime: List[int]) -> int:
        def dfs(i: int) -> int:
            if not g[i]:
                return baseTime[i]
            earliest, latest = inf, -inf
            for j in g[i]:
                a = dfs(j)
                earliest = min(earliest, a)
                latest = max(latest, a)
            own_duration = (latest - earliest) + baseTime[i]
            return latest + own_duration

        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
        return dfs(0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    List<Integer>[] g;
    int[] baseTime;

    long dfs(int i) {
        if (g[i].isEmpty()) {
            return baseTime[i];
        }

        long earliest = Long.MAX_VALUE / 4;
        long latest = Long.MIN_VALUE / 4;

        for (int j : g[i]) {
            long a = dfs(j);
            earliest = Math.min(earliest, a);
            latest = Math.max(latest, a);
        }

        long ownDuration = (latest - earliest) + baseTime[i];
        return latest + ownDuration;
    }

    public long finishTime(int n, int[][] edges, int[] baseTime) {
        this.baseTime = baseTime;
        g = new ArrayList[n];
        Arrays.setAll(g, k -> new ArrayList<>());

        for (int[] e : edges) {
            g[e[0]].add(e[1]);
        }

        return dfs(0);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    long long finishTime(int n, vector<vector<int>>& edges, vector<int>& baseTime) {
        vector<vector<int>> g(n);

        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
        }

        auto dfs = [&](this auto&& dfs, int i) -> long long {
            if (g[i].empty()) {
                return baseTime[i];
            }

            long long earliest = LLONG_MAX / 4;
            long long latest = -LLONG_MAX / 4;

            for (int j : g[i]) {
                long long a = dfs(j);
                earliest = min(earliest, a);
                latest = max(latest, a);
            }

            long long own_duration = (latest - earliest) + baseTime[i];
            return latest + own_duration;
        };

        return dfs(0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func finishTime(n int, edges [][]int, baseTime []int) int64 {
    g := make([][]int, n)

    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
    }

    var dfs func(int) int64

    dfs = func(i int) int64 {
        if len(g[i]) == 0 {
            return int64(baseTime[i])
        }

        var INF int64 = 1 << 62
        var earliest int64 = INF
        var latest int64 = -INF

        for _, j := range g[i] {
            a := dfs(j)
            earliest = min(earliest, a)
            latest = max(latest, a)
        }

        ownDuration := (latest - earliest) + int64(baseTime[i])
        return latest + ownDuration
    }

    return dfs(0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function finishTime(n: number, edges: number[][], baseTime: number[]): number {
    const g: number[][] = Array.from({ length: n }, () => []);

    for (const [u, v] of edges) {
        g[u].push(v);
    }

    const dfs = (i: number): number => {
        if (g[i].length === 0) {
            return baseTime[i];
        }

        let earliest = Number.MAX_SAFE_INTEGER;
        let latest = -Number.MAX_SAFE_INTEGER;

        for (const j of g[i]) {
            const a = dfs(j);
            earliest = Math.min(earliest, a);
            latest = Math.max(latest, a);
        }

        const ownDuration = latest - earliest + baseTime[i];
        return latest + ownDuration;
    };

    return dfs(0);
}

Comments