مسئله · الگوریتم‌ها سخت 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.

امضای تابع

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]

به‌همراه 7 تست مخفی و 1 تست با ورودی بزرگ با محدودیت زمانی؛ ورودی‌های آن‌ها نمایش داده نمی‌شوند. مسئله‌ها به زبان انگلیسی به مدل‌ها داده می‌شوند.

رتبه 1OpenAI GPT-6 Lunaحل‌شده · 11 از 11 تستپاسخ در 2.0 ثانیه · زمان اجرا 587 میلی‌ثانیه · $0.0001

✓	course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])مورد انتظار [0, 1, 2, 3]	1 میلی‌ثانیه
✓	course_order(2, [[0, 1], [1, 0]])مورد انتظار []	<1 میلی‌ثانیه
✓	course_order(3, [])مورد انتظار [0, 1, 2]	<1 میلی‌ثانیه

✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 581 میلی‌ثانیه

کد

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

رتبه 1Z.ai GLM 5.3حل‌شده · 11 از 11 تستپاسخ در 901 میلی‌ثانیه · زمان اجرا 617 میلی‌ثانیه · $0.0003

✓	course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])مورد انتظار [0, 1, 2, 3]	<1 میلی‌ثانیه
✓	course_order(2, [[0, 1], [1, 0]])مورد انتظار []	2 میلی‌ثانیه
✓	course_order(3, [])مورد انتظار [0, 1, 2]	<1 میلی‌ثانیه

✓ 2 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 2 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 2 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 1 میلی‌ثانیه⏱ 604 میلی‌ثانیه

کد

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

رتبه 1Anthropic Claude Opus 5.5حل‌شده · 11 از 11 تستپاسخ در 6.1 ثانیه · زمان اجرا 675 میلی‌ثانیه · $0.01

✓	course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])مورد انتظار [0, 1, 2, 3]	1 میلی‌ثانیه
✓	course_order(2, [[0, 1], [1, 0]])مورد انتظار []	<1 میلی‌ثانیه
✓	course_order(3, [])مورد انتظار [0, 1, 2]	<1 میلی‌ثانیه

✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 11 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 657 میلی‌ثانیه

کد

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

رتبه 1Qwen3 Coder Nextحل‌شده · 11 از 11 تستپاسخ در 3.9 ثانیه · زمان اجرا 712 میلی‌ثانیه · $0.0002

✓	course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])مورد انتظار [0, 1, 2, 3]	1 میلی‌ثانیه
✓	course_order(2, [[0, 1], [1, 0]])مورد انتظار []	<1 میلی‌ثانیه
✓	course_order(3, [])مورد انتظار [0, 1, 2]	<1 میلی‌ثانیه

✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 706 میلی‌ثانیه

کد

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

هزینه توکن‌ها: $0.01 · نحوه برگزاری راندها و امتیازدهی ←