Решение задачи #24. Python Яндекс CodeRun, Тупики

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Тупики.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:

На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).

Дано расписание движения электричек, в котором для каждой электрички указано время ее прибытия, а также время отправления в следующий рейс. Электрички в расписании упорядочены по времени прибытия. Поскольку вокзал — конечная станция, то электричка может стоять на нем довольно долго, в частности, электричка, которая прибывает раньше другой, отправляться обратно может значительно позднее.

Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

Формат ввода (input):
Сначала вводятся число K — количество тупиков и число N — количество электропоездов (1 ≤≤ K ≤≤ 100000, 1 ≤≤ N ≤≤ 100000). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 109109. Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.

Все электрички упорядочены по времени прибытия. Считается, что в нулевой момент времени все тупики на вокзале свободны.

Формат вывода (Output):
Выведите N чисел — по одному для каждой электрички: номер тупика, куда прибудет соответствующая электричка. Если тупиков не достаточно для того, чтобы организовать движение электричек согласно расписанию, выведите два числа: первое должно равняться 0 (нулю), а второе содержать номер первой из электричек, которая не сможет прибыть на вокзал.

Пример работы программы:
input:
1 1
2 5

Output:
1

Решение:

Python

import sys
import heapq

def main():
    # Чтение входных данных
    input = sys.stdin.read
    data = input().split()

    K = int(data[0])  # Количество тупиков
    N = int(data[1])  # Количество электричек

    # Список для хранения расписания электричек
    trains = []
    index = 2
    for _ in range(N):
        arrival = int(data[index])
        departure = int(data[index + 1])
        trains.append((arrival, departure))
        index += 2

    # Минимальная куча (heap) для отслеживания свободных тупиков
    # Изначально все тупики свободны, добавляем их в кучу
    available_tracks = list(range(1, K + 1))
    heapq.heapify(available_tracks)

    # Список кортежей (время освобождения тупика, номер тупика)
    busy_tracks = []

    # Результат — номера тупиков для каждой электрички
    result = []

    for i, (arrival, departure) in enumerate(trains):
        # Освобождаем тупики, которые уже доступны к текущему времени прибытия
        while busy_tracks and busy_tracks[0][0] < arrival:
            _, track_number = heapq.heappop(busy_tracks)
            heapq.heappush(available_tracks, track_number)

        # Если есть свободный тупик, используем его
        if available_tracks:
            track_number = heapq.heappop(available_tracks)
            result.append(track_number)
            heapq.heappush(busy_tracks, (departure, track_number))
        else:
            # Если свободных тупиков нет, выводим 0 и номер электрички
            print(0, i + 1)
            return

    # Выводим результат для всех электричек
    for track_number in result:
        print(track_number)

if __name__ == "__main__":
    main()
	

Объяснение кода

Ввод данных:
Программа начинается с чтения входных данных. Первые два числа — это количество тупиков K и количество электричек N. Затем программа считывает времена прибытия и отправления для каждой электрички и сохраняет их в список trains.

Инициализация структур данных:
Для управления тупиками используется две структуры данных:
available_tracks: куча (heap), содержащая номера свободных тупиков. Изначально все тупики свободны.
busy_tracks: куча, содержащая кортежи (время освобождения, номер тупика) для занятых тупиков.

Основной цикл обработки электричек:
Для каждой электрички проверяется, можно ли освободить какие-либо тупики. Это делается путем удаления из busy_tracks всех тупиков, время освобождения которых меньше времени прибытия текущей электрички.

Если есть свободные тупики (available_tracks не пуст), выбирается тупик с минимальным номером (благодаря свойству кучи), и он назначается текущей электричке. Номер тупика добавляется в результат, а информация о времени освобождения этого тупика добавляется в busy_tracks.

Если свободных тупиков нет, программа выводит 0 и номер текущей электрички, после чего завершает работу.

Вывод результата:
Если все электрички успешно распределены по тупикам, программа выводит номера тупиков для каждой электрички в порядке их прибытия.

Источник решения: hdhai.com