Задание 26. Информатика. ЕГЭ. Основная волна. 10.06.2025-2

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

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит натуральное число \(N\) \((1 \leqslant N \leqslant 1000)\) – количество заявок на проведение мероприятий. Следующие \(N\) строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее \(1440.\) Запишите в ответе два числа: максимальное количество мероприятий, которое можно провести в конференц-зале и самое раннее время начала последнего мероприятия (в минутах от начала суток).

Пример входного файла

\(5\)
\(10 \,\, 150\)
\(100 \,\, 110\)
\(131 \,\, 170\)
\(131 \,\, 180\)
\(120 \,\, 130\)

При таких исходных данных можно провести максимум три мероприятия, например, по заявкам \(2,\) \(3\) и \(5.\) Последнее мероприятие в конференц-зала начнётся самое раннее на \(131\)-й минуте, если состоятся мероприятия по заявкам \(2,\) \(4,\) \(5.\) Ответ: \(3 \,\, 131.\)

fd = open('26_2.txt')
N = int(fd.readline())
meets = []

for line in fd:
    tt = [int(x) for x in line.split()]
    meets.append(tt)
meets.sort(key = lambda x: x[1])
chains  = [0] * N
chains[0] = 1
for i in range(1, N):
    chains[i] = max([chains[j] for j in range(i) if meets[i][0] >= meets[j][1]], default=0) + 1
m = max(chains)
print(m, min([meets[i][0] for i in range(N) if chains[i] == m]))