Skip to content

3965. Finish Time of Tasks I

SourceBiweekly Contest 185 Q3DifficultyMediumRating1698

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

Thinking

The tree is the dependency graph. A node’s finish time needs every child’s finish time, plus its own \(\textit{baseTime}\).

DFS bottom-up: a leaf returns \(\textit{baseTime}[i]\); an internal node takes \(\textit{earliest}\) and \(\textit{latest}\) among children, spends \(\textit{latest}-\textit{earliest}+\textit{baseTime}[i]\), and returns \(\textit{latest}\) plus that duration.

The tree has \(n-1\) edges, so one DFS is the root’s finish time.

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);
}

Solution 2: Explicit Stack

Thinking

The tasks form a tree rooted at \(0\). A non-leaf finish time needs the earliest and latest finish times among its children, plus its own \(\textit{baseTime}\). With \(n \le 10^5\), every child must be finished before the current node is computed. Recursing along a chain uses a call depth equal to the node count and overflows Python once the chain reaches length \(1000\). The stack stores \((\textit{node}, \textit{state})\): state \(0\) writes \(\textit{baseTime}[i]\) for a leaf, and otherwise pushes the exit marker and then the children; state \(1\) reads \(\textit{earliest}\) and \(\textit{latest}\), spends \(\textit{latest}-\textit{earliest}+\textit{baseTime}[i]\), and finishes at \(\textit{latest}\) plus that duration. Child order does not change the earliest or latest value.

Build the tree from \(\textit{edges}\) and store each node's children in an adjacency list \(g\). An edge \(u \to v\) means \(u\) is the parent of \(v\).

Starting at the root \(0\), an explicit stack computes every finish time in postorder:

  • A leaf's finish time is \(\textit{baseTime}[i]\).
  • After every child of a non-leaf is known, let \(\textit{earliest}\) and \(\textit{latest}\) be the minimum and maximum child finish times.
  • The task's own duration is \(\textit{ownDuration} = (\textit{latest} - \textit{earliest}) + \textit{baseTime}[i]\).
  • The finish time of task \(i\) is \(\textit{latest} + \textit{ownDuration}\).

The answer is the finish time of the root. It is guaranteed to be less than \(2^{53}\).

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
18
19
20
21
22
23
24
25
class Solution:
    def finishTime(self, n: int, edges: List[List[int]], baseTime: List[int]) -> int:
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
        fin = [0] * n
        stk = [(0, 0)]
        while stk:
            i, state = stk.pop()
            if state == 0:
                if not g[i]:
                    fin[i] = baseTime[i]
                else:
                    stk.append((i, 1))
                    for j in g[i]:
                        stk.append((j, 0))
            else:
                earliest, latest = inf, -inf
                for j in g[i]:
                    a = fin[j]
                    earliest = min(earliest, a)
                    latest = max(latest, a)
                own = (latest - earliest) + baseTime[i]
                fin[i] = latest + own
        return fin[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
35
36
class Solution {
    public long finishTime(int n, int[][] edges, int[] baseTime) {
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
        }
        long[] fin = new long[n];
        Deque<int[]> stk = new ArrayDeque<>();
        stk.push(new int[] {0, 0});
        while (!stk.isEmpty()) {
            int[] cur = stk.pop();
            int i = cur[0], state = cur[1];
            if (state == 0) {
                if (g[i].isEmpty()) {
                    fin[i] = baseTime[i];
                } else {
                    stk.push(new int[] {i, 1});
                    for (int j : g[i]) {
                        stk.push(new int[] {j, 0});
                    }
                }
            } else {
                long earliest = Long.MAX_VALUE;
                long latest = Long.MIN_VALUE;
                for (int j : g[i]) {
                    earliest = Math.min(earliest, fin[j]);
                    latest = Math.max(latest, fin[j]);
                }
                long ownDuration = (latest - earliest) + baseTime[i];
                fin[i] = latest + ownDuration;
            }
        }
        return fin[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
35
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]);
        }
        vector<long long> fin(n);
        vector<array<int, 2>> stk{{0, 0}};
        while (!stk.empty()) {
            auto [i, state] = stk.back();
            stk.pop_back();
            if (state == 0) {
                if (g[i].empty()) {
                    fin[i] = baseTime[i];
                } else {
                    stk.push_back({i, 1});
                    for (int j : g[i]) {
                        stk.push_back({j, 0});
                    }
                }
            } else {
                long long earliest = LLONG_MAX;
                long long latest = LLONG_MIN;
                for (int j : g[i]) {
                    earliest = min(earliest, fin[j]);
                    latest = max(latest, fin[j]);
                }
                long long ownDuration = (latest - earliest) + baseTime[i];
                fin[i] = latest + ownDuration;
            }
        }
        return fin[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
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])
    }
    fin := make([]int64, n)
    stk := [][2]int{{0, 0}}
    for len(stk) > 0 {
        cur := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        i, state := cur[0], cur[1]
        if state == 0 {
            if len(g[i]) == 0 {
                fin[i] = int64(baseTime[i])
            } else {
                stk = append(stk, [2]int{i, 1})
                for _, j := range g[i] {
                    stk = append(stk, [2]int{j, 0})
                }
            }
        } else {
            var inf int64 = 1 << 62
            earliest, latest := inf, -inf
            for _, j := range g[i] {
                earliest = min(earliest, fin[j])
                latest = max(latest, fin[j])
            }
            ownDuration := (latest - earliest) + int64(baseTime[i])
            fin[i] = latest + ownDuration
        }
    }
    return fin[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
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 fin = Array(n).fill(0);
    const stk: number[][] = [[0, 0]];
    while (stk.length) {
        const [i, state] = stk.pop()!;
        if (state === 0) {
            if (g[i].length === 0) {
                fin[i] = baseTime[i];
            } else {
                stk.push([i, 1]);
                for (const j of g[i]) {
                    stk.push([j, 0]);
                }
            }
        } else {
            let earliest = Number.MAX_SAFE_INTEGER;
            let latest = -Number.MAX_SAFE_INTEGER;
            for (const j of g[i]) {
                earliest = Math.min(earliest, fin[j]);
                latest = Math.max(latest, fin[j]);
            }
            const ownDuration = latest - earliest + baseTime[i];
            fin[i] = latest + ownDuration;
        }
    }
    return fin[0];
}

Comments