Course Schedule with Broken Courses
Google● MediumFULLTIMEONSITE INTERVIEWProblem statement
Courses are numbered from 0 to numCourses - 1. Each pair [course, prerequisite] means the prerequisite must be completed before the course. Some courses are broken.
A course is unavailable if it is broken or if it directly or indirectly depends on an unavailable course. Remove every unavailable course, then return the lexicographically smallest topological ordering of all remaining courses. At each step, choose the smallest numbered currently available course. Return an empty array if the remaining dependency graph contains a cycle.
Function
scheduleCourses(numCourses: int, prerequisites: int[][], brokenCourses: int[]) → int[]Examples
Example 1
numCourses = 6prerequisites = [[1,0],[2,0],[3,1],[4,2],[5,3]]brokenCourses = [1]return = [0,2,4]Broken course 1 makes courses 3 and 5 unavailable. The remaining order is [0,2,4].
Example 2
numCourses = 5prerequisites = [[2,0],[2,1],[3,1]]brokenCourses = []return = [0,1,2,3,4]Courses 0, 1, and 4 start with zero indegree. Choosing the smallest available course at every step gives the displayed order.
Example 3
numCourses = 3prerequisites = [[1,0],[0,1]]brokenCourses = []return = []Courses 0 and 1 form a cycle, so no complete ordering of the remaining graph exists.
Constraints
1 <= numCourses <= 200000.0 <= prerequisites.length <= 300000.- Every prerequisite pair contains two distinct valid course numbers, and pairs do not repeat.
- Broken course numbers are valid and unique.