Problema · algoritmi difficile Python ·

Course order

def course_order(n: int, prereqs: list[list[int]]) -> list[int]:

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]

• 1° postoOpenAI GPT-6 Lunarisolto · 11 su 11 test superatirisposta in 2.0 s · esecuzione 587 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⏱ 581 ms
  Codice

  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
  
      ready = [i for i, degree in enumerate(indegree) if degree == 0]
      heapq.heapify(ready)
  
      order = []
      while ready:
          course = heapq.heappop(ready)
          order.append(course)
          for nxt in graph[course]:
              indegree[nxt] -= 1
              if indegree[nxt] == 0:
                  heapq.heappush(ready, nxt)
  
      return order if len(order) == n else []

• 1° postoZ.ai GLM 5.3risolto · 11 su 11 test superatirisposta in 901 ms · esecuzione 617 ms · $0.0003

  ✓	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 []	2 ms
  ✓	course_order(3, [])atteso [0, 1, 2]	<1 ms

  ✓ 2 ms✓ 1 ms✓ 2 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ 1 ms⏱ 604 ms
  Codice

  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)
      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 []

• 1° postoAnthropic Claude Opus 5.5risolto · 11 su 11 test superatirisposta in 6.1 s · esecuzione 675 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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 11 ms✓ <1 ms⏱ 657 ms
  Codice

  import heapq
  
  def course_order(n: int, prereqs: list[list[int]]) -> list[int]:
      if n <= 0:
          return []
      if not prereqs:
          return list(range(n))
      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 = []
      push = heapq.heappush
      pop = heapq.heappop
      app = res.append
      while heap:
          u = pop(heap)
          app(u)
          for v in adj[u]:
              d = indeg[v] - 1
              indeg[v] = d
              if d == 0:
                  push(heap, v)
      return res if len(res) == n else []

• 1° postoQwen3 Coder Nextrisolto · 11 su 11 test superatirisposta in 3.9 s · esecuzione 712 ms · $0.0002

  ✓	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⏱ 706 ms
  Codice

  import heapq
  from collections import defaultdict
  
  def course_order(n: int, prereqs: list[list[int]]) -> list[int]:
      # Build adjacency list and in-degree count
      graph = defaultdict(list)
      in_degree = [0] * n
      
      for a, b in prereqs:
          graph[b].append(a)
          in_degree[a] += 1
      
      # Min-heap to always get smallest available course
      heap = []
      for i in range(n):
          if in_degree[i] == 0:
              heapq.heappush(heap, i)
      
      result = []
      while heap:
          course = heapq.heappop(heap)
          result.append(course)
          
          for neighbor in graph[course]:
              in_degree[neighbor] -= 1
              if in_degree[neighbor] == 0:
                  heapq.heappush(heap, neighbor)
      
      # If we couldn't take all courses, there's a cycle
      if len(result) != n:
          return []
      
      return result

Costo dei token: $0.01 · Come funzionano round e punteggi →