Défi · algorithmes difficile Python ·
Course order
There are n courses numbered 0..n-1 and prerequisite pairs [a, b] meaning course b must be taken before course a (pairs may repeat). Return the order in which to take all courses such that whenever several courses are available, the smallest-numbered one is taken first; this order is unique. Return [] if it's impossible to take all courses. Up to 100,000 courses and 300,000 pairs.
Signature
def course_order(n: int, prereqs: list[list[int]]) -> list[int]:Exemples
course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) # -> [0, 1, 2, 3]
course_order(2, [[0, 1], [1, 0]]) # -> []
course_order(3, []) # -> [0, 1, 2]Plus 7 tests masqués et 1 test de performance sous contrainte de temps ; leurs entrées ne sont pas affichées. Les défis sont soumis aux modèles en anglais.
#1Z.ai GLM 5.3résolu · 11 sur 11 testsréponse en 1.3 s · exécution 555 ms · $0.0003 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])attendu [0, 1, 2, 3] 4 ms ✓ course_order(2, [[0, 1], [1, 0]])attendu [] <1 ms ✓ course_order(3, [])attendu [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 546 msCode
import heapq def course_order(n: int, prereqs: list[list[int]]) -> list[int]: adj = [[] for _ in range(n)] indeg = [0] * n for a, b in prereqs: adj[b].append(a) indeg[a] += 1 heap = [i for i in range(n) if indeg[i] == 0] heapq.heapify(heap) res = [] while heap: c = heapq.heappop(heap) res.append(c) for nxt in adj[c]: indeg[nxt] -= 1 if indeg[nxt] == 0: heapq.heappush(heap, nxt) return res if len(res) == n else []#1OpenAI GPT-6 Lunarésolu · 11 sur 11 testsréponse en 2.1 s · exécution 580 ms · $0.0001 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])attendu [0, 1, 2, 3] <1 ms ✓ course_order(2, [[0, 1], [1, 0]])attendu [] <1 ms ✓ course_order(3, [])attendu [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 572 msCode
import heapq def course_order(n: int, prereqs: list[list[int]]) -> list[int]: graph = [[] for _ in range(n)] indegree = [0] * n for a, b in prereqs: graph[b].append(a) indegree[a] += 1 available = [i for i, degree in enumerate(indegree) if degree == 0] heapq.heapify(available) order = [] while available: course = heapq.heappop(available) order.append(course) for nxt in graph[course]: indegree[nxt] -= 1 if indegree[nxt] == 0: heapq.heappush(available, nxt) return order if len(order) == n else []#3SpaceXAI Grok Build 0.1résolu · 11 sur 11 testsréponse en 16 s · exécution 831 ms · $0.0052 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])attendu [0, 1, 2, 3] <1 ms ✓ course_order(2, [[0, 1], [1, 0]])attendu [] 1 ms ✓ course_order(3, [])attendu [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 823 msCode
import heapq from collections import defaultdict def course_order(n: int, prereqs: list[list[int]]) -> list[int]: if n == 0: return [] graph = defaultdict(set) indegree = [0] * n for a, b in prereqs: if a not in graph[b]: graph[b].add(a) indegree[a] += 1 heap = [i for i in range(n) if indegree[i] == 0] heapq.heapify(heap) order = [] while heap: node = heapq.heappop(heap) order.append(node) for nei in graph[node]: indegree[nei] -= 1 if indegree[nei] == 0: heapq.heappush(heap, nei) if len(order) == n: return order else: return []#3MoonshotAI Kimi K2.7 Coderésolu · 11 sur 11 testsréponse en 43 s · exécution 917 ms · $0.01 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])attendu [0, 1, 2, 3] 1 ms ✓ course_order(2, [[0, 1], [1, 0]])attendu [] <1 ms ✓ course_order(3, [])attendu [0, 1, 2] <1 ms ✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 908 msCode
import heapq def course_order(n: int, prereqs: list[list[int]]) -> list[int]: adj = [[] for _ in range(n)] indeg = [0] * n seen = set() for a, b in prereqs: if not (0 <= a < n and 0 <= b < n): continue key = (b, a) if key in seen: continue seen.add(key) adj[b].append(a) indeg[a] += 1 heap = [i for i, d in enumerate(indeg) if d == 0] heapq.heapify(heap) order = [] while heap: u = heapq.heappop(heap) order.append(u) for v in adj[u]: indeg[v] -= 1 if indeg[v] == 0: heapq.heappush(heap, v) return order if len(order) == n else []
Coût en jetons: $0.02 · Déroulement et calcul des scores →