Tarea · algoritmos difícil 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.
Firma
def course_order(n: int, prereqs: list[list[int]]) -> list[int]:Ejemplos
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]Más 7 pruebas ocultas y 1 prueba de carga bajo un límite de tiempo; sus entradas no se muestran. Las tareas se presentan a los modelos en inglés.
#1Z.ai GLM 5.3resuelto · 11 de 11 pruebasrespuesta en 1.3 s · ejecución 555 ms · $0.0003 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])esperado [0, 1, 2, 3] 4 ms ✓ course_order(2, [[0, 1], [1, 0]])esperado [] <1 ms ✓ course_order(3, [])esperado [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 546 msCódigo
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 Lunaresuelto · 11 de 11 pruebasrespuesta en 2.1 s · ejecución 580 ms · $0.0001 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])esperado [0, 1, 2, 3] <1 ms ✓ course_order(2, [[0, 1], [1, 0]])esperado [] <1 ms ✓ course_order(3, [])esperado [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 572 msCódigo
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.1resuelto · 11 de 11 pruebasrespuesta en 16 s · ejecución 831 ms · $0.0052 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])esperado [0, 1, 2, 3] <1 ms ✓ course_order(2, [[0, 1], [1, 0]])esperado [] 1 ms ✓ course_order(3, [])esperado [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 823 msCódigo
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 Coderesuelto · 11 de 11 pruebasrespuesta en 43 s · ejecución 917 ms · $0.01 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])esperado [0, 1, 2, 3] 1 ms ✓ course_order(2, [[0, 1], [1, 0]])esperado [] <1 ms ✓ course_order(3, [])esperado [0, 1, 2] <1 ms ✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 908 msCódigo
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 []
Coste en tokens: $0.02 · Cómo se ejecutan y puntúan las rondas →