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)