#2050

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Parallel Courses III

Solve Parallel Courses III by finding the minimum number of months to complete all courses using graph-based topological sorting.

array dynamic programming graph topological sort

Problem Statement

You are given an integer n representing the number of courses, with courses numbered from 1 to n. Additionally, you're provided with a 2D array, relations, where relations[j] = [prevCoursej, nextCoursej] indicates that course prevCoursej must be completed before course nextCoursej. You are also given an array time, where time[i] represents the months required to finish course (i+1).

Your task is to determine the minimum number of months needed to complete all courses, respecting the given prerequisite relationships. The solution must optimize the order of course completion to minimize total time, considering that some courses may run in parallel.

Examples

Example 1

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]

Output: 8

The figure above represents the given graph and the time required to complete each course. We start course 1 and course 2 simultaneously at month 0. Course 1 takes 3 months and course 2 takes 2 months to complete respectively. Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

Example 2

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]

Output: 12

The figure above represents the given graph and the time required to complete each course. You can start courses 1, 2, and 3 at month 0. You can complete them after 1, 2, and 3 months respectively. Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months. Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months. Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.

Constraints

1 <= n <= 5 * 104
0 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)
relations[j].length == 2
1 <= prevCoursej, nextCoursej <= n
prevCoursej != nextCoursej
All the pairs [prevCoursej, nextCoursej] are unique.
time.length == n
1 <= time[i] <= 104
The given graph is a directed acyclic graph.

Solution Approach

Topological Sorting with Indegree

The core of the solution involves determining a topological order of the courses based on the given prerequisites. You can process the courses in a way that allows you to complete prerequisites first. Using a graph, calculate the indegree of each course and utilize a priority queue or DFS to ensure courses are completed in the optimal order.

Course Completion Scheduling

Once courses are processed in topological order, the time to complete a course is determined by the maximum time of its prerequisites plus its own completion time. For each course, compute the earliest month it can be completed by considering the completion time of prerequisite courses and adding the time required for the course itself.

Handling Parallel Courses

Since multiple courses can run in parallel once their prerequisites are completed, it's important to track which courses can start at the same time. By scheduling courses optimally, we can ensure that the total completion time is minimized, balancing parallelism and prerequisites.

Complexity Analysis

Metric	Value
Time	O(n + e)
Space	O(n + e)

The time complexity is O(n + e) due to the need to process each course and each relation. The space complexity is also O(n + e) for storing the graph and the indegree of each course. This approach ensures efficient handling even for large input sizes, up to the constraints limit of 5 * 10^4 courses.

What Interviewers Usually Probe

Look for the candidate’s understanding of topological sorting and how it applies to course scheduling.
Check if the candidate efficiently handles course dependencies and parallel execution of independent courses.
Observe how well the candidate identifies the minimum completion time, factoring in both prerequisites and parallel courses.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly implement the topological sort, which can lead to incorrect processing order of courses.
Not properly handling parallelism between courses, which can result in unnecessarily long completion times.
Forgetting to calculate the total time based on the prerequisites of each course, leading to incorrect results.

Follow-up variants

Add a constraint where some courses must be completed before others in a cycle, testing the ability to handle cycles in the graph.
Modify the problem to include more dynamic scheduling conditions, such as time constraints for each course based on external factors.
Change the problem to consider weighted prerequisites where different prerequisite courses have different times affecting the start times.

FAQ

What is the primary algorithm used in Parallel Courses III?

The primary algorithm is topological sorting combined with graph indegree management to determine the optimal course completion order.

How does parallelism affect the course completion time?

Parallelism allows multiple courses to be completed simultaneously once their prerequisites are finished, reducing the overall time needed.

What is the expected time complexity of solving Parallel Courses III?

The time complexity is O(n + e), where n is the number of courses and e is the number of prerequisite relationships.

What is the key challenge in Parallel Courses III?

The key challenge is scheduling courses in a way that respects all prerequisite relationships while minimizing the total completion time.

Can Parallel Courses III be solved using a brute force approach?

While a brute force approach might work for small inputs, it would be inefficient for larger datasets, and topological sorting is necessary for optimal performance.

terminal

Solution

Solution 1: Topological Sorting + Dynamic Programming

First, we construct a directed acyclic graph based on the given prerequisite course relationships, perform topological sorting on this graph, and then use dynamic programming to find the minimum time required to complete all courses according to the results of the topological sorting.

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        g = defaultdict(list)
        indeg = [0] * n
        for a, b in relations:
            g[a - 1].append(b - 1)
            indeg[b - 1] += 1
        q = deque()
        f = [0] * n
        ans = 0
        for i, (v, t) in enumerate(zip(indeg, time)):
            if v == 0:
                q.append(i)
                f[i] = t
                ans = max(ans, t)
        while q:
            i = q.popleft()
            for j in g[i]:
                f[j] = max(f[j], f[i] + time[j])
                ans = max(ans, f[j])
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return ans

Continue Practicing

#2328 number of increasing paths in a grid #1728 cat and mouse ii #2115 find all possible recipes from given supplies