Course Schedule

Средняя№207

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

207 Course ScheduleРазбор · 1×

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

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

Пара [a, b] ставит b раньше a: [1, 0], [2, 1], [3, 2], [1, 3], [4, 0], [5, 4], [5, 3] дают стрелки 0 → 1, 1 → 2, 2 → 3, 3 → 1, 0 → 4, 4 → 5, 3 → 5. Считаем стрелки, входящие в каждый курс

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

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

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

  1. Курс попадает в очередь, только когда пройдены все курсы перед ним, поэтому курсы выходят из очереди в порядке, который соблюдает каждую пару.
  2. В цикле каждый курс ждёт предыдущий по кругу. Ни у одного из них степень не дойдёт до 0, поэтому ни один не будет пройден — как и курсы, которые идут после цикла.
  3. Значит, все n курсов пройдены ровно тогда, когда цикла нет: достаточно посчитать пройденные курсы.

Сложность

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

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

Решить на LeetCode ↗

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