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

Решение.

Сохраним приложенный текстовый файл под именем data.txt. Первая строка задаёт параметры задачи; её нельзя считать обычной записью данных. В программе нумерация элементов списка начинается с нуля, а номера из условия сохраняются без сдвига.

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

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

Тот же обмен показывает: после любого фиксированного числа выбранных мероприятий жадное расписание заканчивается не позже любого другого. Сохраним первые k − 1 выбранных заявок и время T их завершения. Последней может стать любая заявка с началом не раньше T.

Для максимального перерыва выбираем среди таких заявок наибольшее время начала S. Ответ по второму критерию равен S − T. Более позднее завершение предпоследнего мероприятия только сократит этот перерыв и сузит список доступных последних заявок.

Таким образом, второй критерий оптимизируется среди расписаний уже максимального размера; он не должен менять первичный выбор количества. Сортировка занимает O(N log N), два прохода — O(N), память O(N).

Полная программа на Python:

with open("data.txt", encoding="utf-8-sig") as f:
    n = int(f.readline())
    events = [tuple(map(int, f.readline().split())) for _ in range(n)]
events.sort(key=lambda event: (event[1], event[0]))
chosen = []
finish = 0
for start, end in events:
    if start >= finish:
        chosen.append((start, end))
        finish = end
k = len(chosen)
prefix_finish = chosen[-2][1]
best = max(start - prefix_finish for start, end in events if start >= prefix_finish)
print(k, best)

Проверка результата.

Максимальное количество k = 26. Первые k − 1 мероприятий заканчиваются в T = 1249. Последняя выбранная заявка занимает время 1260…1271.

Перерыв 1260 − 1249 = 11.

Одно достигающее ответ расписание задаётся следующими номерами заявок, отсчитываемыми от первой строки после заголовка: 284, 691, 367, 955, 716, 162, 299, 22, 338, 258, 812, 898, 70, 920, 435, 729, 818, 375, 323, 310, 254, 703, 756, 797, 643, 794. Все соседние интервалы в этом порядке совместимы.

Ответ: 26 11.