Задание №26: как работает программа отбора мероприятий

В задаче о конференц-зале ↗ заявка содержит время начала и окончания мероприятия. Зал вмещает одно мероприятие; следующее может начаться сразу после окончания предыдущего. Требуется сначала максимальное количество мероприятий, затем самое позднее окончание последнего среди расписаний с этим количеством. Ниже объясняется программа из разбора сортировки и выбора объектов: какие данные хранит каждая переменная и почему одного отбора недостаточно.

Данные до запуска программы

Приложение B1238c.zip содержит файл 2_26.txt. После распаковки он помещается в рабочую папку программы. Первая строка задаёт количество заявок; следующие строки содержат по два целых числа — начало и конец в минутах от начала суток. Порядок полей сохраняется: начало стоит первым, конец вторым.

Для наблюдения за переменными удобно использовать пять заявок из иллюстрации условия. Это самостоятельный маленький пример, не первые пять строк полного файла. Номер в таблице нужен только для объяснения; программа не читает его как третье число.

Чтение и хранение пар

Программа открывает текстовый файл под именем f. Метод readline() читает следующую строку; int превращает её в целое число. В переменную n попадает количество заявок, поэтому заголовок файла не становится мероприятием.

with open("2_26.txt") as f:
    n = int(f.readline())
    events = []
    for _ in range(n):
        row = f.readline()
        pair = map(
            int, row.split()
        )
        events.append(
            tuple(pair)
        )

Пустой список events постепенно заполняется заявками. Цикл range(n) выполняет тело ровно n раз; имя _ показывает, что номер повторения здесь не используется. Для строки 100 110 вызов split() выделяет две строки с числами, а map(int, ...) преобразует каждую в число.

tuple(pair) собирает числа в кортеж, после чего append добавляет одну целую пару в конец списка. В маленьком примере первым элементом списка будет (10, 150), вторым — (100, 110). После выхода из блока with файл закрывается, а прочитанный список остаётся доступен.

Сортировка по нужному полю

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

def end_time(event):
    return event[1]

events.sort(key=end_time)

Функция end_time получает одну заявку event и возвращает её второй элемент. Индексы Python начинаются с нуля: event[0] — начало, event[1] — конец. Параметр key сообщает сортировке, какое значение сравнивать. Весь список меняет порядок, но внутри каждой пары начало и конец остаются на местах.

Для пяти заявок порядок становится 2,5,1,3,4: окончания равны 110,130,150,170,180. Теперь после текущей заявки не встретится другая с более ранним окончанием. Это позволяет принимать допустимые заявки сразу.

Первый проход: максимум количества

Переменная finish хранит время, до которого зал уже занят выбранными мероприятиями. Вначале оно равно нулю. Список chosen хранит только окончания выбранных заявок, не пары и не номера из таблицы.

chosen = []
finish = 0
for start, end in events:
    if start >= finish:
        chosen.append(end)
        finish = end

При каждом повторении пара распаковывается в start и end. Проверка сравнивает начало новой заявки с концом уже выбранной. Если начало не раньше finish, пересечения нет: конец добавляется в chosen и становится новой границей занятости. Равенство разрешено условием, поэтому используется >=.

Если проверка ложна, обе строки внутри if пропускаются. Ни список, ни граница не меняются: неподходящая заявка не занимает зал. Затем цикл переходит к следующей паре.

Длина списка равна трём. Заявка 4 была пропущена из-за пересечения с уже взятой заявкой 3, хотя она совместима с первыми двумя. Это различие становится существенным для второго требования: конец 170 ещё не максимально поздний.

Граница для замены последнего мероприятия

Теперь количество увеличивать уже не требуется. Последнее мероприятие можно заменить другим, сохранив первые два. Их окончание образует границу допустимого начала замены. Переменная prefix хранит конец этой начальной части расписания.

prefix = 0
if len(chosen) >= 2:
    prefix = chosen[-2]

Отрицательные индексы отсчитываются от конца: chosen[-1] — последнее окончание, chosen[-2] — предпоследнее. В примере prefix получает 130. При единственном выбранном мероприятии сохранённая начальная часть пуста, поэтому граница остаётся нулевой. Проверка длины не позволяет обращаться к несуществующему предпоследнему элементу.

Почему сохраняется именно начальная часть первого отбора? Её мероприятия заканчиваются как можно раньше среди последовательностей той же длины. Поэтому любая последняя заявка из расписания максимальной длины подходит и после этой части. Замена не теряет потенциально самый поздний конец.

Второй проход: поиск позднейшего конца

Переменная latest хранит наибольший конец среди уже проверенных допустимых замен. Снова просматриваются все заявки, включая пропущенные первым проходом:

latest = 0
for start, end in events:
    if start >= prefix:
        latest = max(
            latest, end
        )

Заявки 2, 5 и 1 начинаются раньше 130, поэтому не рассматриваются как последние после сохранённых двух мероприятий. Заявка 3 начинается в 131 и поднимает latest до 170. Заявка 4 тоже начинается в 131; её конец больше, поэтому latest становится 180.

Во втором проходе prefix не изменяется. Здесь сравниваются альтернативы для одного последнего места, а не строится новая цепочка. Список chosen тоже остаётся прежним: для ответа нужны количество и лучший конец, а не само окончательное расписание.

print(len(chosen), latest)

Маленький пример даёт 3\quad180: заявки 2, 5 и 4. В полном файле 990 заявок. Первый проход выбирает 53, предпоследнее окончание равно 1020. Первоначальная последняя заявка идёт с 1023 до 1057, а замена — с 1026 до 1300. Ответ полного файла: 53\quad1300.

Возможные ловушки

Взять chosen[-1] вместо chosen[-2]. Тогда поиск начинается после окончания всех выбранных мероприятий и фактически пытается найти дополнительное. В маленьком примере граница станет 170, заявка 131\text{–}180 не пройдёт, а latest останется нулём. Для замены последнего нужна граница перед ним.

Остановиться после первого прохода. Вывод finish даст 170 вместо 180 в иллюстрации. Раннее окончание помогает увеличить количество, но второй критерий требует противоположного выбора для последнего места.

Прочитать второе число как длительность. latest хранит минуту от начала суток. Вычитание начала последней заявки изменит смысл ответа. Также нельзя заменить >= на >: такая правка запрещает разрешённый стык мероприятий.

Технические правила: работа с файлами ↗ и ключ сортировки ↗. Обоснование отбора относится к условиям этой задачи; другую цель или запрет стыка нужно учитывать отдельно.