Задание EGEINFB1238C: Сортировка, отбор и моделирование

Решение.
В исходном файле 990 заявок. Мероприятия совместимы, когда начало следующего не меньше окончания предыдущего; при равенстве оба разрешены. Сначала максимизируем количество, и только среди расписаний этого количества ищем самое позднее окончание.

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

Обоснование первого критерия. Среди всех заявок, которые можно поставить следующими, самая рано заканчивающаяся оставляет не меньше времени для продолжения, чем любая другая. В оптимальном расписании можно заменить следующий выбор этой заявкой, не потеряв последующие мероприятия. Повторяя обмен, получаем жадное расписание максимальной длины. Кроме того, его j-я заявка заканчивается не позже j-й заявки любого другого допустимого расписания такой длины.

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

В данном файле m = 53, первые 52 выбранные заявки заканчиваются в момент 1020. Среди заявок с началом не раньше 1020 наибольшее окончание равно 1300. Не нужно требовать совпадения времени начала последней заявки с началом прежней последней; достаточно совместимости с префиксом.

Программа Python; data.txt — файл заявок из архива:

with open("data.txt", encoding="utf-8-sig") as f:
    n = int(f.readline())
    events = [tuple(map(int, line.split())) for line in f if line.strip()]
assert len(events) == n
ordered = sorted(events, key=lambda event: (event[1], event[0]))
chosen = []
finish = 0
for start, end in ordered:
    if start >= finish:
        chosen.append((start, end))
        finish = end
prefix_finish = chosen[-2][1] if len(chosen) > 1 else 0
latest = max(end for start, end in events if start >= prefix_finish)
print(len(chosen), latest)

Проверка. Независимое динамическое программирование для каждой заявки вычисляет наибольшее количество мероприятий расписания, заканчивающегося ею. Затем среди заявок с количеством 53 выбирается наибольшее окончание. Оно также равно 1300.

Одно достигающее обоих критериев расписание задаётся номерами заявок в исходном файле, без строки заголовка:
654, 327, 105, 903, 20, 312, 639, 204, 258, 261, 450, 249, 918, 705, 983, 589, 537, 572, 899, 588, 587, 58, 655, 502, 31, 861, 367, 827, 656, 34, 546, 925, 175, 198, 22, 569, 763, 868, 732, 314, 975, 649, 687, 250, 632, 9, 638, 965, 123, 140, 850, 570, 101.
Все 53 заявки различны; начало каждой следующей не меньше окончания предыдущей.

Ответ: 53 1300.