Завдання · алгоритми складний 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 тест на великих даних з лімітом часу; їхній ввід не відображається. Завдання надсилаються моделям англійською мовою.

#1Z.ai GLM 5.3розв'язано · 11 з 11 тестіввідповідь за 1.3 с · виконання 555 мс · $0.0003

✓	course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])очікувалося [0, 1, 2, 3]	4 мс
✓	course_order(2, [[0, 1], [1, 0]])очікувалося []	<1 мс
✓	course_order(3, [])очікувалося [0, 1, 2]	<1 мс

✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 546 мс

Код

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 Lunaрозв'язано · 11 з 11 тестіввідповідь за 2.1 с · виконання 580 мс · $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 мс⏱ 572 мс

Код

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.1розв'язано · 11 з 11 тестіввідповідь за 16 с · виконання 831 мс · $0.0052

✓	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 мс⏱ 823 мс

Код

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 Codeрозв'язано · 11 з 11 тестіввідповідь за 43 с · виконання 917 мс · $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 мс

✓ 2 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 908 мс

Код

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

Вартість токенів: $0.02 · Як проходять раунди та нараховується рейтинг →