Minimum time taken by each job to be completed given by a Directed Acyclic Graph
Problem Statement
Given a Directed Acyclic Graph (DAG) where each vertex represents a job that takes 1 unit of time, find the minimum time required to complete each job. A job can only start after all its prerequisite jobs are completed.
Example:
- Input:
V = 6, Edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]] - Output:
[1, 2, 2, 3, 4, 5](time to complete each job)
Noob-Friendly Explanation
Imagine a factory assembly line. Some steps can only start after other steps are done. For example, you can't paint a car until it's assembled, and you can't assemble it until parts are made.
Each job takes 1 unit of time. If a job depends on two other jobs, it can only start after BOTH are done. So its completion time is: max(completion time of prerequisites) + 1.
Jobs with no prerequisites can start at time 1 (immediately). The question is: for each job, what's the earliest it can be finished?
Approach 1: Brute Force (DFS for Each Node)
Intuition
For each node, run a DFS to find the longest path from any source (node with no incoming edges) to that node. The longest path length + 1 gives the completion time.
Algorithm
- Build the adjacency list.
- For each node, compute the longest path from any source using DFS.
- The completion time for each node is its longest path distance + 1.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class JobTimeBruteForce {
public static int[] jobCompletionTime(int V, int[][] edges) {
// Build reverse adjacency list (to look at prerequisites)
List<List<Integer>> reverseAdj = new ArrayList<>();
for (int i = 0; i < V; i++) {
reverseAdj.add(new ArrayList<>());
}
for (int[] edge : edges) {
reverseAdj.get(edge[1]).add(edge[0]); // reverse edge
}
int[] time = new int[V];
int[] memo = new int[V];
Arrays.fill(memo, -1);
for (int i = 0; i < V; i++) {
time[i] = dfs(reverseAdj, memo, i);
}
return time;
}
static int dfs(List<List<Integer>> reverseAdj, int[] memo, int node) {
if (memo[node] != -1) return memo[node];
int maxPrereqTime = 0;
for (int prereq : reverseAdj.get(node)) {
maxPrereqTime = Math.max(maxPrereqTime, dfs(reverseAdj, memo, prereq));
}
memo[node] = maxPrereqTime + 1;
return memo[node];
}
public static void main(String[] args) {
int V = 6;
int[][] edges = {{0,1},{0,2},{1,3},{2,3},{3,4},{4,5}};
int[] result = jobCompletionTime(V, edges);
System.out.println(Arrays.toString(result)); // [1, 2, 2, 3, 4, 5]
}
}Complexity Analysis
- Time Complexity: O(V × (V + E)) in the worst case without memoization, O(V + E) with memoization.
- Space Complexity: O(V + E) — for the reverse adjacency list and memo array.
Approach 2: Optimal (Topological Sort + BFS)
Intuition
Use Kahn's algorithm (BFS topological sort). Process jobs in topological order. For each job with in-degree 0, set time = 1. When processing a job, update all dependent jobs' times as max(current time, parent time + 1).
Algorithm
- Build adjacency list and compute in-degrees.
- Add all nodes with in-degree 0 to the queue with time = 1.
- Process queue: for each neighbor, update time and reduce in-degree.
- When in-degree becomes 0, add to queue.
import java.util.*;
public class JobTimeOptimal {
public static int[] jobCompletionTime(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[V];
int[] time = new int[V];
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
inDegree[edge[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (inDegree[i] == 0) {
queue.add(i);
time[i] = 1; // jobs with no prerequisites complete at time 1
}
}
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
// Neighbor can start only after current job finishes
time[neighbor] = Math.max(time[neighbor], time[node] + 1);
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.add(neighbor);
}
}
}
return time;
}
public static void main(String[] args) {
int V = 6;
int[][] edges = {{0,1},{0,2},{1,3},{2,3},{3,4},{4,5}};
int[] result = jobCompletionTime(V, edges);
System.out.println(Arrays.toString(result)); // [1, 2, 2, 3, 4, 5]
}
}Complexity Analysis
- Time Complexity: O(V + E) — each vertex and edge is processed once.
- Space Complexity: O(V + E) — for the adjacency list, in-degree array, and queue.