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] = [u_i, v_i] indicates that task u_i is the parent of task v_i.

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 <= 10⁵
edges.length = n - 1
edges[i] == [u_i, v_i]
0 <= u_i, v_i <= n - 1
u_i!= v_i
The input is generated such that edges represents a valid tree.
baseTime.length == n
1 <= baseTime[i] <= 10⁵
The finish time of every task is guaranteed to be less than 2⁵³.

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.

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 $(node, 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.

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

// Solution 2
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];
    }
}

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

// Solution 2
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];
    }
};

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)


# Solution 2
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]

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

// Solution 2
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]
}

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

3965 - Finish Time of Tasks I

3965. Finish Time of Tasks I

Description

Solutions

Solution 1: DFS

Solution 2: Explicit Stack

All Problems

All Solutions

Welcome to Subscribe On Youtube

3965. Finish Time of Tasks I

Description

Solutions

Solution 1: DFS

Solution 2: Explicit Stack

All Problems

All Solutions