26. Прикладная задача: #298077

Два мероприятия совместимы, если конец одного не позже начала другого. Максимальное количество находится классической жадностью: сортируем по времени окончания и берём каждое, которое начинается не раньше конца предыдущего взятого.

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

Поэтому считаем динамику: для каждого мероприятия $i$ находим $cnt[i]$ — сколько мероприятий максимум умещается в цепочке, которая заканчивается именно этим. Максимум по всем $cnt$ даёт ответ на первый вопрос, обозначим его $K$. Затем среди всех мероприятий с $cnt[i] = K$ берём наибольшее время окончания: каждое такое мероприятие может оказаться последним в некотором оптимальном расписании.

f = open('26-21.txt')
n = int(f.readline())
ev = [tuple(map(int, f.readline().split())) for _ in range(n)]
ev.sort(key=lambda x: x[1])                  # по времени окончания

cnt = [0] * n            # макс. число мероприятий в цепочке, кончающейся i-м
for i, (a, b) in enumerate(ev):
    best = 0
    for k in range(i):
        if ev[k][1] <= a and cnt[k] > best:   # конец не позже начала
            best = cnt[k]
    cnt[i] = best + 1

K = max(cnt)
last = max(b for (a, b), c in zip(ev, cnt) if c == K)

print(K, last)   # 19 1362

Проверка. Заявок $912$, жадный подсчёт тоже даёт $19$ мероприятий, но его расписание освобождает зал уже на $1088$-й минуте — почти на пять часов раньше найденного оптимума. При этом $1362$ меньше, чем самое позднее окончание в файле вообще ($1400$): то мероприятие в цепочку из $19$ штук не встраивается. На типовом примере из условия программа выдаёт $3$ и $180$.