Course Schedule II

Средняя№210

Есть n курсов с номерами от 0 до n − 1 и список пар [a, b]: курс b нужно пройти раньше курса a. Нужно вернуть порядок, в котором можно пройти все курсы; подойдёт любой такой. Если его нет, вернуть пустой список. Наш пример: 6 курсов и пары [0, 3], [0, 5], [1, 0], [2, 5], [4, 1], [4, 2]. Один из ответов — [3, 5, 0, 2, 1, 4].

210 Course Schedule IIРазбор · 1×

Пример: 6 курсов и 6 пар. Стрелки появляются по мере чтения пар: b → a для [a, b]; число над курсом — сколько курсов он ещё ждёт.

001020304050очередьначало слева—порядок—
ждёт другие курсыв очередитекущий курс; b из парыкуда ведёт стрелкав порядке

Стрелок пока нет: у каждого курса пустой список следующих

01/53
сначала · назад · пуск · шаг
Скорость
1function findOrder(n, prerequisites):
2 graph = an empty list for each course
3 indegree = 0 for each course
4 for each [a, b] in prerequisites:
5 graph[b].pushBack(a)
6 increase indegree[a] by 1
7 queue = courses with indegree 0
8 order = []
9 while queue is not empty:
10 course = queue.popFront()
11 order.pushBack(course)
12 for next in graph[course]:
13 decrease indegree[next] by 1
14 if indegree[next] is 0:
15 queue.pushBack(next)
16 if length(order) < n:
17 return []
18 return order
состояние
a
–
b
–
indegree
–
queue
–
order
–
course
–
next
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Пара [a, b] — это стрелка b → a, поэтому входящая степень курса — это число курсов, которые должны идти раньше него.
  2. Курс попадает в порядок только после всех курсов, от которых в него идут стрелки, поэтому порядок соблюдает каждую пару.
  3. Если есть цикл, у курсов в нём степень никогда не станет 0: порядок выйдет короче n, и ответ — пустой список.

Сложность

Время O(n + p) для n курсов и p пар: каждую пару читаем один раз, каждый курс попадает в очередь не больше одного раза, по каждой стрелке проходим один раз. Память O(n + p) на стрелки, степени, очередь и порядок.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.