Задание 26 ЕГЭ по информатике: расписание интервалов

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

Следующая задача в кабинете

Проверьте ответ здесь. Появится кнопка к другим заданиям этого номера.

К упражнениям
Скачать 26-intervaly.txt

Файл содержит 220 пар. Граница допустима: интервалы 10–20 и 20–35 можно выбрать оба.

Задания

1Расписание одного зала

В первой строке файла N, затем N пар «начало конец» в минутах от открытия. Если одно мероприятие кончилось в минуту t, другое можно начать в t. Запишите через пробел максимум мероприятий и самое позднее время окончания последнего события среди расписаний такого размера.

Решение

Жадный выбор по ближайшему окончанию даёт максимум k мероприятий. После первых k − 1 событий их последнее окончание самое раннее среди всех префиксов такой длины. Значит, на последнее место можно взять любое мероприятие, начинающееся не раньше этого момента. Из них берём самое позднее окончание. Сложность O(n log n) из-за сортировки.

from pathlib import Path

lines = Path("26-intervaly.txt").read_text(encoding="ascii").splitlines()
n = int(lines[0])
intervals = [tuple(map(int, line.split())) for line in lines[1:]]
assert len(intervals) == n

intervals.sort(key=lambda interval: interval[1])
ends = [0]
for start, finish in intervals:
    if start >= ends[-1]:
        ends.append(finish)

count = len(ends) - 1
earliest_prefix_end = ends[-2]
latest_finish = max(finish for start, finish in intervals if start >= earliest_prefix_end)
print(count, latest_finish)

Дальше по теме

Источники