Course Order Feasibility
Problem
A programme has n courses numbered from 0, plus a list of pairs where the pair course, before means that course cannot be taken until before is finished. Decide whether an order exists that lets a student finish all n courses. Return true when such an order exists and false when the requirements contradict each other.
Examples
Input: n = 3, pairs = [[1, 0], [2, 1]]
Output: True
Why: the order 0, 1, 2 satisfies both requirementsInput: n = 2, pairs = [[1, 0], [0, 1]]
Output: False
Why: each course waits for the other, so neither can startInput: n = 1, pairs = []
Output: True
Why: edge case, a course with no requirements can always be takenHints
0 / 3
Model the requirements as arrows between courses and ask what shape in that picture would make an order impossible.
A course becomes takeable exactly when nothing it depends on is left, so tracking how many unfinished requirements each course still has is more useful than tracking the requirements themselves.
Count the outstanding requirements for every course and start with those at zero. Repeatedly take a ready course, mark it finished, and decrease the counter of every course that depended on it, adding any that reach zero. If the number finished falls short of n, some courses are trapped in a cycle.
Solution
The requirements form a directed graph, and a valid order exists precisely when that graph has no cycle. Peeling off courses whose outstanding requirement count has reached zero simulates taking them, and releases their dependants one at a time. Any course stuck in a cycle never reaches zero, so a shortfall in the finished count proves the requirements contradict each other. Time is O(n + p) for n courses and p pairs, and space is O(n + p).
from collections import deque
def can_finish(n, pairs):
graph = [[] for _ in range(n)] # course -> courses unlocked by it
waiting = [0] * n # how many requirements are still open
for course, before in pairs:
graph[before].append(course)
waiting[course] += 1
ready = deque(c for c in range(n) if waiting[c] == 0)
done = 0
while ready: # take a course with nothing left to wait for
c = ready.popleft()
done += 1
for nxt in graph[c]:
waiting[nxt] -= 1
if waiting[nxt] == 0: ready.append(nxt)
return done == n # leftovers mean a cycle blocked them
print(can_finish(3, [[1, 0], [2, 1]])) # -> True
print(can_finish(2, [[1, 0], [0, 1]])) # -> False
print(can_finish(1, [])) # -> TrueStuck on the idea rather than the code? Topological Sort covers it.