Parallel Courses

Medium

Topological Sort

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCoursei, nextCoursei], representing a prerequisite relationship between course prevCoursei and course nextCoursei: course prevCoursei has to be taken before course nextCoursei.

In one semester, you can take any number of courses as long as you have taken all the prerequisites in the previous semesters for the courses you are taking.

Return the minimum number of semesters needed to take all courses. If there is no way to take all the courses, return -1.

The insight: Each "semester" corresponds to one level in topological sort. Courses with in-degree 0 can be taken in the current semester. After taking them, we update in-degrees and move to the next semester. The number of semesters equals the longest path in the DAG.

Real-world analogy: Think of a university student planning their course load. They can take multiple courses simultaneously in one semester, as long as all prerequisites are satisfied. The minimum time to graduate is determined by the longest prerequisite chain.

Example 1

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

Output: 2

Explanation: Semester 1: Take courses 1 and 2 (no prerequisites). Semester 2: Take course 3 (requires 1 and 2, both done).

Example 2

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

Output: -1

Explanation: There is a cycle: 1 -> 2 -> 3 -> 1. It is impossible to take all courses.

Example 3

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

Output: 4

Explanation: Each course depends on the previous one, forming a chain. Must take one course per semester.

Constraints

•1 <= n <= 5000
•1 <= relations.length <= 5000
•relations[i].length == 2
•1 <= prevCoursei, nextCoursei <= n
•prevCoursei != nextCoursei
•All the pairs [prevCoursei, nextCoursei] are unique

Show Hints (6)

Hint 1: Model this as a graph problem. What do nodes and edges represent?

Hint 2: This is topological sort, but we need to count the number of "levels" or "rounds".

Hint 3: In Kahn's algorithm, process all nodes with in-degree 0 at once (one semester).

Hint 4: After each semester, update in-degrees and find new courses available.

Hint 5: Count the number of semesters (BFS levels) until all courses are taken.

Hint 6: If we cannot take all courses, there must be a cycle. Return -1.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?