107. Parallel Courses — Minimum Semesters
Take any number of currently eligible courses in parallel during a semester. A course becomes eligible only after its prerequisites have been completed in earlier semesters.
Courses finishing in the same semester cannot unlock a dependent for that same semester. Prerequisite cycles make a complete schedule impossible.
Example 1
Input
n=5, relations=[[0,2],[1,2],[2,3]]
Output
3
Explanation: Semester 1 takes 0,1,4; semester 2 takes 2; semester 3 takes 3. Independent work does not add semesters.
Example 2
Input
n=3, relations=[[0,1],[0,1],[1,2]]
Output
3
Explanation: Both 0→1 occurrences discharge together; 1 still waits until the next semester.
Example 3
Input
n=3, relations=[[0,1],[1,0]]
Output
-1
Explanation: Course 2 can finish, but the remaining cycle prevents a full schedule.
Constraints
0 <= n <= 1050 <= edge occurrences <= 2 * 1050 <= vertex label < n
Hints
Hint 1
Unlimited parallel work suggests complete readiness batches.
Hint 2
Use incoming counts, but freeze the queue length before each semester.
Hint 3
Compare the last batch number with longest prerequisite-chain length and verify full completion.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Independent courses share the first semester
5
[[0,2],[1,2],[2,3]]
3