Minimum Time to Finish Project

Problem Overview

Tasks run in parallel unless a dependency forces an order, so the project takes as long as the slowest chain of dependent tasks.

Intuition

Tasks run in parallel unless a dependency forces an order, so the project takes as long as the slowest chain of dependent tasks. A task can start only after all its prerequisites finish, which means its finish time is its own duration plus the latest finish among those prerequisites. Processing tasks in topological order guarantees every prerequisite is final before it is used. If the dependencies form a cycle, some tasks never become free and the project cannot finish.

Algorithm

1Count the indegree of each task and group outgoing edges into flat arrays so each task lists the tasks that wait on it.
2Set each finish time to the task duration and queue every task with indegree 0.
3Pop a task and update the answer with its finish time.
4For each waiting task, set its finish time to the larger of its current value and this finish plus its own duration. Lower its indegree and queue it when that reaches 0.
5If fewer than n tasks were processed, return -1. Otherwise return the largest finish time.

Example Walkthrough

Input: duration = [3,2,5], dependencies = [[0,2],[1,2]]

1. Tasks 0 and 1 have no prerequisites, so they finish at 3 and 2.
2. Task 2 waits for both, so it starts at 3 and finishes at 3 + 5 = 8.
3. Every task was processed, so there is no cycle.

Output: 8

Common Pitfalls

• Independent tasks overlap. Adding every duration together overstates the time.
• A task finish time must use the maximum over all prerequisites, not just the last one processed.
• A cycle leaves some tasks with indegree above 0 forever. Check the processed count before returning.
• A list of boxed integers for every task is slower than one shared edge array indexed by start offsets.

Minimum Time to Finish Project.java

Java

// Approach: Kahn's topological sort. A dependency [u, v] means v starts
// after u finishes, so finish[v] is its duration plus the largest finish
// among its prerequisites. Edges are stored in flat arrays (compressed
// adjacency), and the queue is a plain int array. If some task never reaches
// indegree 0, the dependencies contain a cycle and the project cannot finish.
// Complexity: O(n + m) time, O(n + m) extra space.
class Solution {
    public int minTime(int[] duration, int[][] dependencies) {
        int n = duration.length;
        int m = dependencies.length;

        int[] start = new int[n + 1];
        int[] indeg = new int[n];
        for (int[] d : dependencies) {
            start[d[0] + 1]++;
            indeg[d[1]]++;
        }
        for (int i = 0; i < n; i++)
            start[i + 1] += start[i];

        int[] next = new int[m];
        int[] fill = new int[n];
        System.arraycopy(start, 0, fill, 0, n);
        for (int[] d : dependencies)
            next[fill[d[0]]++] = d[1];

        int[] finish = new int[n];
        int[] queue = new int[n];
        int head = 0;
        int tail = 0;
        for (int i = 0; i < n; i++) {
            finish[i] = duration[i];
            if (indeg[i] == 0)
                queue[tail++] = i;
        }

        int ans = 0;
        while (head < tail) {
            int u = queue[head++];
            ans = Math.max(ans, finish[u]);
            for (int e = start[u]; e < start[u + 1]; e++) {
                int v = next[e];
                finish[v] = Math.max(finish[v], finish[u] + duration[v]);
                if (--indeg[v] == 0)
                    queue[tail++] = v;
            }
        }
        return tail < n ? -1 : ans;
    }
}

Was this solution helpful?