JavaScript Coding Test Course, Finding the Critical Path

Problem Description

You are managing a project management system where various tasks are interconnected. Each task must be performed for a specific duration, and certain tasks can only start after others have been completed. Implement an algorithm to determine the minimum time required for the project to be completed based on these relationships.

The project consists of the following information:

  • n : number of tasks
  • dependencies : an array representing the dependency relationships between each task
  • times : an array of the time required to perform each task

The function format is as follows:

function criticalPath(n, dependencies, times) {
    // Write your code here.
}

Example Input

n = 5
dependencies = [[1, 0], [2, 1], [3, 1], [3, 2], [4, 3]]
times = [3, 2, 5, 1, 2]
Input: criticalPath(n, dependencies, times)

Example Output

Output: 11

Problem Solving Approach

To solve this problem, the following steps should be taken:

1. Graph Modeling

Represent the tasks and their dependency relationships as a graph. Each task can be represented as a vertex, and the dependencies as edges.

2. Topological Sort

Determine the order of task execution through topological sorting of the given graph. Topological sorting is the process of finding a linear arrangement of all vertices in a directed graph.

3. Calculate the Longest Path

Use the topological sort to calculate the start time of each task and ultimately find the minimum time required for all tasks to be completed.

Implementation Code

Below is the JavaScript code that implements the above approach:

function criticalPath(n, dependencies, times) {
    const adjList = Array.from({length: n}, () => []);
    const inDegree = Array(n).fill(0);
    
    // 1. Build the graph and calculate in-degrees
    for (const [next, prev] of dependencies) {
        adjList[prev].push(next);
        inDegree[next]++;
    }
    
    // 2. Create a queue for topological sorting
    const queue = [];
    const timeToComplete = Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        timeToComplete[i] = times[i];
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }
    
    // 3. Calculate the longest path
    let maxTime = 0;

    while (queue.length) {
        const current = queue.shift();
        maxTime = Math.max(maxTime, timeToComplete[current]);

        for (const neighbor of adjList[current]) {
            timeToComplete[neighbor] = Math.max(timeToComplete[neighbor], timeToComplete[current] + times[neighbor]);
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    return maxTime;
}

Code Explanation

Now, let’s look at each part of the code:

1. Build the graph and calculate in-degrees

First, based on the dependency relationships given in the input, an adjacency list is created, and the in-degrees of each vertex are calculated. Tasks with an in-degree of 0 can start immediately, so they are added to the queue.

2. Topological sorting and longest path calculation

Tasks are removed one by one from the queue, updating the longest completion times for their subsequent tasks. If the in-degree of a subsequent task becomes 0, it is added back to the queue. After processing all tasks, the longest recorded time is the critical path.

Time Complexity Analysis

This algorithm explores each vertex and edge of the graph once, so its time complexity is O(V + E), where V is the number of tasks and E is the number of dependency relationships between tasks.

Final Thoughts

Finding the critical path is an important element in project management and scheduling, and it is widely used in industry. This problem allows you to understand the concepts of graphs and topological sorting, while also developing your ability to solve complex problems in JavaScript.

Additional Practice Problems

Now, to test your skills, try solving the following problems:

  1. Implement an algorithm to track changes in the critical path when the dependency relationships between tasks change.
  2. Consider not only the time required for tasks but also their costs. What would be your approach to finding the optimal path in this case?
  3. How can you apply topological sorting when the graph has a different structure (e.g., directed acyclic graph)?

References

If you want to know more about the critical path problem, check the links below: