Parallel Courses III

class Solution {
public:
    unordered_map<int, vector<int>> adjacencyList;
    vector<int> cachedResults;

    int calculateMinTime(int totalTasks, vector<vector<int>>& prerequisites, vector<int>& taskDurations) {
        for (auto& relation : prerequisites) {
            int prev = relation[0] - 1;
            int next = relation[1] - 1;
            adjacencyList[prev].push_back(next);
        }

        cachedResults = vector(totalTasks, -1);
        int maxTime = 0;
        for (int task = 0; task < totalTasks; task++) {
            maxTime = max(maxTime, findTime(task, taskDurations));
        }

        return maxTime;
    }

    int findTime(int task, vector<int>& taskDurations) {
        if (cachedResults[task] != -1) {
            return cachedResults[task];
        }

        if (adjacencyList[task].empty()) {
            return taskDurations[task];
        }

        int maxDuration = 0;
        for (int subsequentTask : adjacencyList[task]) {
            maxDuration = max(maxDuration, findTime(subsequentTask, taskDurations));
        }

        cachedResults[task] = taskDurations[task] + maxDuration;
        return taskDurations[task] + maxDuration;
    }
};

In the provided C++ solution for finding the minimum time needed to complete all tasks with given prerequisites and individual task durations, the approach is centered around using Depth-First Search (DFS) with memoization. The implementation involves the following key components:

• Adjacency List Creation: Initializes an adjacency list from the prerequisite pairs, which map each task to its subsequent tasks.

• Memoization Setup: Utilizes a vector cachedResults to store the calculated durations for each task, avoiding redundant calculations and improving efficiency.

• DFS Execution: Implements a recursive function findTime() which computes the minimum time required to finish a task including the time required for its prerequisites. This function checks if the result is already computed (memoization). Otherwise, it calculates the time by recursively determining the maximum time required for all subsequent tasks and adds the duration of the current task to this maximum.

• Overall Time Calculation: Loops through all tasks and uses the findTime() function to determine the time required for each task. Tracks and updates the maximum time encountered.

This approach not only efficiently calculates the result but also ensures that all dependencies are accounted for by using the DFS mechanism to delve deep into each chain of tasks as specified by the prerequisites before summing up the times, ensuring the correct order of operations as mandated by the prerequisites list. The use of memoization significantly enhances performance by avoiding repeat computations for each task.

class TaskScheduler {
    Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
    Map<Integer, Integer> cache = new HashMap<>();
    
    public int calculateMinTime(int n, int[][] relations, int[] durations) {
        for (int i = 0; i < n; i++) {
            adjacencyList.put(i, new ArrayList<>());
        }
        
        for (int[] relation: relations) {
            int start = relation[0] - 1;
            int end = relation[1] - 1;
            adjacencyList.get(start).add(end);
        }
        
        int result = 0;
        for (int node = 0; node < n; node++) {
            result = Math.max(result, depthFirstSearch(node, durations));
        }

        return result;
    }
    
    public int depthFirstSearch(int node, int[] durations) {
        if (cache.containsKey(node)) {
            return cache.get(node);
        }
        
        if (adjacencyList.get(node).isEmpty()) {
            return durations[node];
        }
        
        int maxTime = 0;
        for (int adjacent: adjacencyList.get(node)) {
            maxTime = Math.max(maxTime, depthFirstSearch(adjacent, durations));
        }
        
        cache.put(node, durations[node] + maxTime);
        return durations[node] + maxTime;
    }
}

The provided Java code defines a solution to finding the minimum time required to finish all courses where certain courses depend on the completion of other courses before they can be started. This problem is modeled using a directed graph where each node represents a course and each directed edge indicates a prerequisite relationship.

Here's an overview of how the solution works:

• A class TaskScheduler includes helper methods to calculate the course completion time using Depth First Search (DFS) and caching.

• It makes use of two main data structures:

  • An adjacency list (adjacencyList), which stores the graph in the form of a list of nodes (courses), where each node points to other nodes (subsequent courses).
  • A cache (cache), a hashmap used to store computed times for nodes to avoid recomputation, thereby optimizing performance.

• The method calculateMinTime initializes the adjacency list and processes the input array relations to build the graph by populating the adjacency list. After building the graph, it iterates over each node and uses recursion to compute the time required for each node using the method depthFirstSearch.

• The method depthFirstSearch calculates the course completion time for each node recursively:

  • If the course (node) does not have any subsequent courses, its completion time is just its duration.
  • If it does have subsequent courses, the method calculates the maximum completion time using the times of subsequent courses retrieved via further recursive calls.
  • Each computed time for a node is cached to optimize subsequent calls.

• The final result is determined by taking the maximum of the computed times from all nodes, giving the total minimum time needed to complete all courses.

This implementation is especially effective due to its use of memoization (caching) and its clear separation of concerns between graph construction and processing logic. Each functionality is encapsulated in dedicated methods, and intermediate results are stored efficiently, ensuring that the solution is both understandable and performant.

class Solution:
    def minCompletionTime(self, tasks: int, dependencies: List[List[int]], durations: List[int]) -> int:
        @cache
        def explore(task):
            if not workflow[task]:
                return durations[task]
            
            max_duration = 0
            for adjacent in workflow[task]:
                max_duration = max(max_duration, explore(adjacent))

            return durations[task] + max_duration
        
        workflow = defaultdict(list)
        for (start, end) in dependencies:
            workflow[start - 1].append(end - 1)
        
        total_max = 0
        for i in range(tasks):
            total_max = max(total_max, explore(i))

        return total_max

This program effectively computes the minimum time required to complete all tasks given their dependencies and individual durations. It is implemented in Python using a depth-first search (DFS) methodology to traverse through each task's dependencies to calculate the completion times.

• Start by defining a recursive function explore using the @cache decorator to memoize results and optimize the DFS approach:

  • If a task has no further dependencies (workflow[task] is empty), directly return its duration from durations[task].
  • If there are dependent tasks, recursively call explore for each of them, keeping track of the maximum duration calculated so far.
  • Accumulate the maximum duration of dependencies with the duration of the current task to determine the total completion time for this task.

• Initialize a dictionary workflow using defaultdict(list) to store tasks as keys and their respective dependent tasks as values.

  • Populate this dictionary from the list of dependencies. Adjust for 0-based indexing by subtracting 1 from each task number.

• Determine the overall maximum time required to complete all tasks:

  • Iterate through each task and update a total_max variable with the maximum time returned by the explore function for each task.

• The function finally returns the total_max, representing the minimum time to complete all tasks considering their given durations and dependencies. This solution efficiently handles task relationships and individual processing times to calculate the comprehensive completion schedule.