Practice/Snowflake/Leetcode 1136. Parallel Courses

Leetcode 1136. Parallel Courses

CodingOptional

Problem

You are a student planning your course schedule. There are n courses numbered from 1 to n, and some courses have prerequisites that must be completed before you can enroll in them.

You are given an integer n representing the total number of courses and a 2D array relations where relations[i] = [prevCourse, nextCourse] indicates that you must complete prevCourse before taking nextCourse.

In each semester, you can take any number of courses simultaneously, as long as you have completed all the prerequisites for those courses. Your goal is to determine the minimum number of semesters needed to complete all n courses.

If it is impossible to complete all courses due to circular dependencies, return -1.

Requirements

1. Return the minimum number of semesters required to complete all courses
2. Return -1 if there exists a cycle in the prerequisite relationships (making completion impossible)
3. Handle cases where courses have no prerequisites
4. Consider that multiple courses can be taken in the same semester if their prerequisites are satisfied

Constraints

• 1 <= n <= 5000
• 0 <= relations.length <= 5000
• relations[i].length == 2
• 1 <= prevCourse, nextCourse <= n
• prevCourse != nextCourse
• All prerequisite pairs are unique

Examples

Example 1:

Input: n = 3, relations = [[1,3],[2,3]] Output: 2 Explanation: Semester 1: Take courses 1 and 2 Semester 2: Take course 3 (prerequisites 1 and 2 are now complete)

Example 2:

Input: n = 4, relations = [] Output: 1 Explanation: There are no prerequisites, so all 4 courses can be taken in a single semester.

Example 3:

Input: n = 3, relations = [[1,2],[2,3],[3,1]] Output: -1 Explanation: The courses form a cycle (1→2→3→1), so it's impossible to satisfy all prerequisites.