Minimum Time to Finish Project with Dependencies Using Topological Sort in Java

Introduction

In a software project, there may be many modules that need to be completed. Some modules can be developed independently, while some modules can be started only after another module has been completed.

For example:

Module 0 → Module 1 → Module 2

Here, Module 1 can start only after Module 0 is completed, and Module 2 can start only after Module 1 is completed.

At the same time, if two modules do not depend on each other, they can be developed simultaneously.

The goal is to find the minimum time required to complete the entire project.

This problem can be solved efficiently using:

Directed Graph
Topological Sorting
BFS (Kahn's Algorithm)
Dynamic Programming

Problem Understanding

We are given two arrays:

1. `duration[]`

duration[i] represents the time required to complete module i.

For example:

duration = [10, 20, 30]

This means:

Module 0 → 10 months
Module 1 → 20 months
Module 2 → 30 months

2. `dependencies[][]`

Each dependency is represented as:

[u, v]

This means:

u → v

Module v can start only after module u is completed.

For example:

dependencies = [[0, 1], [1, 2]]

means:

0 → 1 → 2

Important Observation

We should not add the duration of every module.

Why?

Because independent modules can be completed at the same time.

For example:

      → Module 1 (20)
Module 0
      → Module 2 (30)

If Module 0 takes 10 months:

Module 0 = 10

After Module 0 finishes, Modules 1 and 2 can work simultaneously.

Therefore:

Module 1 finishes at 10 + 20 = 30
Module 2 finishes at 10 + 30 = 40

The entire project finishes at:

40 months

not:

10 + 20 + 30 = 60

So, we need to find the longest dependency path.

This longest path determines the total project completion time.

Graph Representation

We represent every module as a vertex.

Every dependency is represented as a directed edge.

For:

dependencies = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]

the graph looks conceptually like:

The important dependency chain is:

5 → 2 → 3 → 1

Its duration is:

20 + 30 + 10 + 20
= 80

Therefore, the answer is:

Why Topological Sorting?

A module can be processed only after all of its dependencies are completed.

This is exactly the property handled by Topological Sorting.

For a directed graph, a topological ordering places every node before the nodes that depend on it.

For example:

0 → 1 → 2

A valid topological order is:

0, 1, 2

We can use Kahn's Algorithm, which is a BFS-based topological sorting algorithm.

What is Indegree?

indegree[v] represents the number of dependencies that module v has.

For example:

0 → 2
1 → 2

Module 2 has two incoming edges.

Therefore:

indegree[2] = 2

Module 2 can be processed only when:

indegree[2] == 0

That means all its dependencies have been completed.

Step 1: Build the Graph

We create an adjacency list.

List<List<Integer>> graph = new ArrayList<>();

for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}

For every dependency:

for (int[] dependency : dependencies) {

    int u = dependency[0];
    int v = dependency[1];

    graph.get(u).add(v);
    indegree[v]++;
}

If we have:

[0, 1]

we create:

0 → 1

and increase:

indegree[1]++;

Step 2: Find Modules With No Dependencies

A module with:

indegree[i] == 0

does not depend on any other module.

Therefore, it can start immediately.

We add these modules to the queue:

Queue<Integer> queue = new LinkedList<>();

for (int i = 0; i < n; i++) {

    if (indegree[i] == 0) {
        finishTime[i] = duration[i];
        queue.offer(i);
    }
}

For example:

0 → 1

Module 0 has:

indegree[0] = 0

So Module 0 can start immediately.

Its finish time is:

duration[0]

Step 3: Store the Finish Time

We use:

int[] finishTime

where:

finishTime[i]

means:

The earliest time at which module i can be completed.

For a module with no dependencies:

finishTime[i] = duration[i];

For example:

duration[0] = 10

Then:

finishTime[0] = 10

Step 4: Process Modules Using BFS

Now we process the queue.

while (!queue.isEmpty()) {

    int u = queue.poll();
    processed++;

    ...
}

For every module u, we look at the modules that depend on it.

for (int v : graph.get(u)) {

Suppose:

u → v

Module v can start only after module u finishes.

Therefore:

finishTime[v] =
    Math.max(finishTime[v],
             finishTime[u] + duration[v]);

Why Do We Use Math.max()?

This is one of the most important parts of the solution.

Consider:

Now suppose:

1 → 3
2 → 3

So Module 3 depends on both Module 1 and Module 2.

Imagine:

finishTime[1] = 30
finishTime[2] = 50
duration[3] = 10

Module 3 cannot start at 30 because Module 2 is still running.

It must wait until both dependencies are finished.

Therefore:

start time of Module 3 = max(30, 50)
                       = 50

Then:

finishTime[3] = 50 + 10
              = 60

That's why we use:

Math.max(
    finishTime[v],
    finishTime[u] + duration[v]
);

Step 5: Reduce the Indegree

After processing the edge:

u → v

we have completed one dependency of v.

Therefore:

indegree[v]--;

If:

indegree[v] == 0

then all dependencies of v have been completed.

So we add it to the queue:

if (indegree[v] == 0) {
    queue.offer(v);
}

Step 6: Detect a Cycle

A project cannot be completed if there is a cyclic dependency.

For example:

0 → 1
↑   ↓
└── 2

or:

0 → 1 → 2 → 0

Every module is waiting for another module.

Therefore, no module can be processed initially.

We keep track of how many modules were processed:

int processed = 0;

Every time we remove a module from the queue:

processed++;

At the end:

if (processed != n) {
    return -1;
}

If fewer than n modules were processed, a cycle exists.

Complete Java 21 Solution

import java.util.*;

class Solution {

    public int minTime(int[] duration, int[][] dependencies) {

        int n = duration.length;

        // Create adjacency list
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // Calculate indegree
        int[] indegree = new int[n];

        for (int[] dependency : dependencies) {

            int u = dependency[0];
            int v = dependency[1];

            graph.get(u).add(v);
            indegree[v]++;
        }

        // Earliest completion time of each module
        int[] finishTime = new int[n];

        Queue<Integer> queue = new LinkedList<>();

        // Add modules having no dependencies
        for (int i = 0; i < n; i++) {

            if (indegree[i] == 0) {

                finishTime[i] = duration[i];

                queue.offer(i);
            }
        }

        int processed = 0;
        int answer = 0;

        // Topological sorting using BFS
        while (!queue.isEmpty()) {

            int u = queue.poll();

            processed++;

            // Update project completion time
            answer = Math.max(answer, finishTime[u]);

            // Process dependent modules
            for (int v : graph.get(u)) {

                finishTime[v] = Math.max(
                    finishTime[v],
                    finishTime[u] + duration[v]
                );

                indegree[v]--;

                // All dependencies are completed
                if (indegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // Cycle exists
        if (processed != n) {
            return -1;
        }

        return answer;
    }
}

Dry Run

Consider:

duration = [10, 20, 30, 10, 30, 20]

dependencies =
[
    [5, 2],
    [5, 0],
    [4, 0],
    [4, 1],
    [2, 3],
    [3, 1]
]

The important path is:

5 → 2 → 3 → 1

Their durations are:

Therefore:

20 + 30 + 10 + 20
= 80

The modules on different branches can execute simultaneously.

Therefore:

Answer = 80

Example With a Cycle

Input:

duration = [5, 5, 5]

dependencies =
[
    [0, 1],
    [1, 2],
    [2, 0]
]

Graph:

0 → 1 → 2
↑         ↓
└─────────┘

There is no module with:

indegree == 0

So the queue remains empty.

No module can be processed.

Therefore:

processed != n

and the function returns:

-1

Why This Solution Is Efficient

A simple approach might try to calculate different dependency paths repeatedly. That can become very expensive when there are up to 10^5 modules and 2 * 10^5 dependencies.

Our approach processes:

Every module once.
Every dependency once.

Therefore:

Time Complexity = O(n + m)

where:

n = number of modules
m = number of dependencies

The graph, indegree array, finish-time array, and queue require:

Space Complexity = O(n + m)

Key Takeaways

The important concepts used in this problem are:

Directed Graph
Modules are vertices and dependencies are directed edges.
Indegree
Tells us how many unfinished dependencies a module has.
Topological Sort
Processes modules only after their dependencies are completed.
BFS / Kahn's Algorithm
Used to perform the topological sorting.
Dynamic Programming
finishTime[] stores the earliest completion time of every module.
Longest Dependency Path
Since modules can execute simultaneously, the overall project time is determined by the longest dependency chain.
Cycle Detection
If all modules cannot be processed, the dependency graph contains a cycle and we return -1.

The main formula to remember is:

finishTime[v] = Math.max(
    finishTime[v],
    finishTime[u] + duration[v]
);

This formula ensures that a module waits for its slowest/last dependency before it can finish.

This explanation is suitable for learning the problem from beginner level to interview level, especially the connection between Topological Sort + DP + Critical Path.

Introduction

Problem Understanding

1. duration[]

2. dependencies[][]

1. `duration[]`

2. `dependencies[][]`