Finish Time of Tasks II - Solution & Explanation

Problem Overview: You are given multiple tasks where some tasks depend on others. Each task can start only after all its prerequisite tasks finish. The goal is to determine the final completion time considering these dependencies and task durations.

Approach 1: Brute Force Dependency Simulation (High Time Complexity)

A direct strategy repeatedly scans all tasks and checks whether their prerequisites have finished. If every dependency of a task is completed, the task can start and its finish time becomes start + duration. The algorithm keeps updating finish times until no further updates occur. This works but performs many redundant checks across the dependency list. With n tasks and m dependencies, repeated scans can push the time complexity toward O(n * m) with O(n) space. It mainly helps build intuition about dependency resolution.

Approach 2: Topological Sort + Dynamic Programming (Optimal, O(V+E))

The task dependency graph forms a Directed Acyclic Graph (DAG). A natural solution is to process tasks in topological order so every prerequisite is handled before the dependent task. Build an adjacency list and track indegree counts for each node. Start with tasks that have indegree = 0. For each processed task, update its neighbors by computing the earliest finish time using finish[next] = max(finish[next], finish[curr] + duration[next]). Push neighbors into the queue when their indegree becomes zero. This guarantees each edge and node is processed once, giving O(V + E) time and O(V + E) space. The key insight is that the finish time of a task equals the longest path ending at that node in the DAG.

Approach 3: DFS + Memoization (Longest Path in DAG)

Another way to compute completion times is depth‑first search with memoization. For every task, recursively compute the maximum completion time of all prerequisite paths. Cache the computed finish time so each node is evaluated once. This transforms the problem into a longest‑path calculation in a DAG. With memoization and adjacency lists, the complexity remains O(V + E) time and O(V) recursion/memo space. This approach is concise but recursion depth can be a limitation for very large graphs.

Recommended for interviews: The expected solution is topological sorting combined with dynamic programming. It clearly models dependency ordering and computes earliest completion times in one pass. Interviewers often like to see the brute force idea first to demonstrate understanding of the dependency constraints, then the optimized DAG approach using graph traversal and topological sort. The finish‑time update step is essentially a longest‑path calculation on a DAG, which also connects to dynamic programming concepts.