Introduction
In many companies related to software development, coding tests have become a mandatory part of the hiring process.
In particular, Java is one of the preferred programming languages in many companies.
In this post, we will take a closer look at how to solve the ‘Finding the Critical Path’ problem using Java.
The critical path refers to finding the longest path in a directed graph and plays an important role in scheduling in project management tools.
Problem Description
In the given directed graph, each node represents a task, and each edge indicates the dependencies between tasks.
Our goal is to find the longest path from the starting node to the final node in the directed graph.
For example, when the execution time of each task is given, the essence of the problem is to determine the maximum time it takes to complete the project.
Input Format
- Integer N: Number of tasks (1 ≤ N ≤ 10,000)
- Integer M: Number of dependencies (1 ≤ M ≤ 100,000)
- Execution time of each task: Given in the form of an array
- Dependency information: Given in the form of an array (a → b: Task a can only be performed after task b is completed)
Output Format
Output the maximum time required to complete the final task.
Example
**Input**:
5 4
[2, 3, 4, 1, 5]
[
(0, 1),
(1, 2),
(1, 3),
(3, 4)
]
**Output**:
10
In this example, the maximum path is based on the continuity of None: 2 (from 0 to 1) + 3 (from 1 to 2) + 5 (from 3 to 4), requiring a total time of 10 to complete the final task.
Approach to the Problem
To solve the ‘Finding the Critical Path’ problem, we can utilize graph traversal algorithms.
Generally, we will use Topological Sort to determine the order of tasks and then calculate the cumulative time for each node to determine the final time.
The overall solution proceeds through the following steps:
- Create the graph: Construct a directed graph connecting each task to its dependent tasks.
- Topological Sorting: Sort the dependent tasks to allow for sequential execution of tasks.
- Calculate time: Accumulate the time taken for each task to compute the time for the final target task.
Step 1: Create the Graph
We create the graph using the inputted dependency information.
Each task is viewed as a vertex, and edges are established according to their dependencies.
In Java, we can represent the graph using an ArrayList.
List> graph = new ArrayList<>();
int[] indegree = new int[N];
int[] time = new int[N];
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<>());
}
// Construct graph based on dependency information
// Add edge from a to b through (a, b)
for (int[] dep : dependencies) {
graph.get(dep[0]).add(dep[1]);
indegree[dep[1]]++;
time[dep[0]] = taskTimes[dep[0]];
}
Step 2: Topological Sorting
Once the graph is created, we start exploring the vertices using topological sorting, beginning with nodes that have an indegree of 0.
This can typically be implemented using a queue.
Queue queue = new LinkedList<>();
for (int i = 0; i < N; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int[] dp = new int[N]; // Store completion time for each task
while (!queue.isEmpty()) {
int u = queue.poll();
dp[u] = Math.max(dp[u], time[u]);
for (int v : graph.get(u)) {
indegree[v]--;
dp[v] = Math.max(dp[v], dp[u] + time[v]);
if (indegree[v] == 0) {
queue.offer(v);
}
}
}
Step 3: Calculate Time
When we reach the final task, the maximum value in the dp array represents the maximum time required to complete the project.
int result = 0;
for (int t : dp) {
result = Math.max(result, t);
}
System.out.println(result);
Java Code
import java.util.*;
public class CriticalPath {
public static void main(String[] args) {
// Input processing
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[] taskTimes = new int[N];
for (int i = 0; i < N; i++) {
taskTimes[i] = sc.nextInt();
}
List> graph = new ArrayList<>();
int[] indegree = new int[N];
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph.get(a).add(b);
indegree[b]++;
}
// Topological sorting and time calculation
Queue queue = new LinkedList<>();
for (int i = 0; i < N; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int[] dp = new int[N];
while (!queue.isEmpty()) {
int u = queue.poll();
dp[u] = Math.max(dp[u], taskTimes[u]);
for (int v : graph.get(u)) {
indegree[v]--;
dp[v] = Math.max(dp[v], dp[u] + taskTimes[v]);
if (indegree[v] == 0) {
queue.offer(v);
}
}
}
// Calculate maximum time
int result = Arrays.stream(dp).max().getAsInt();
System.out.println(result);
}
}
Conclusion
In this lecture, we covered the process of solving the critical path finding problem using Java.
We learned how to represent the dependencies of each task using graph theory and to calculate the completion time of the final task.
As such, a step-by-step approach is crucial in solving algorithmic problems, and this can lead to good results in actual coding tests.
We will continue to write articles covering various algorithms, so please stay tuned for more.