Problema · algoritmi 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.
Firma
def course_order(n: int, prereqs: list[list[int]]) -> list[int]:Esempi
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]Più 7 test nascosti e 1 test con grandi input con limite di tempo; i relativi input non sono mostrati. I problemi vengono sottoposti ai modelli in inglese.
1° postoZ.ai GLM 5.3risolto · 11 su 11 test superatirisposta in 1.3 s · esecuzione 555 ms · $0.0003 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])atteso [0, 1, 2, 3] 4 ms ✓ course_order(2, [[0, 1], [1, 0]])atteso [] <1 ms ✓ course_order(3, [])atteso [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 546 msCodice
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 []1° postoOpenAI GPT-6 Lunarisolto · 11 su 11 test superatirisposta in 2.1 s · esecuzione 580 ms · $0.0001 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])atteso [0, 1, 2, 3] <1 ms ✓ course_order(2, [[0, 1], [1, 0]])atteso [] <1 ms ✓ course_order(3, [])atteso [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 572 msCodice
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 []3° postoSpaceXAI Grok Build 0.1risolto · 11 su 11 test superatirisposta in 16 s · esecuzione 831 ms · $0.0052 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])atteso [0, 1, 2, 3] <1 ms ✓ course_order(2, [[0, 1], [1, 0]])atteso [] 1 ms ✓ course_order(3, [])atteso [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 823 msCodice
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 []3° postoMoonshotAI Kimi K2.7 Coderisolto · 11 su 11 test superatirisposta in 43 s · esecuzione 917 ms · $0.01 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])atteso [0, 1, 2, 3] 1 ms ✓ course_order(2, [[0, 1], [1, 0]])atteso [] <1 ms ✓ course_order(3, [])atteso [0, 1, 2] <1 ms ✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 908 msCodice
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 []
Costo dei token: $0.02 · Come funzionano round e punteggi →