Карточки
Тесты
Главная
Курсы
Подписка
26. Прикладная задача: #298083
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Два мероприятия совместимы, если конец одного не позже начала другого. Максимальное количество даёт классическая жадность: сортируем по времени окончания и берём каждое, которое начинается не раньше конца предыдущего взятого.
Второй вопрос жадность не решает: расписаний с максимальным количеством мероприятий много, а перерыв нужен наибольший по всем таким расписаниям. Поэтому считаем динамику: для каждого мероприятия $i$ находим $cnt[i]$ — сколько мероприятий максимум умещается в цепочке, которая заканчивается именно этим. Максимум по всем $cnt$ даёт ответ на первый вопрос, обозначим его $K$.
Теперь пара последних мероприятий. Последнее — это любое $j$ с $cnt[j] = K$, а предыдущее — любое совместимое с ним $i$, у которого $cnt[i] = K-1$: тогда цепочка из $K-1$ мероприятий заканчивается на $i$, а $j$ добавляется последним. Перерыв равен разности между началом $j$ и концом $i$, берём наибольший.
f = open('26-24.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)
gap = 0
for j, (a, b) in enumerate(ev):
if cnt[j] != K: # j должно быть последним в цепочке
continue
for i in range(j):
if cnt[i] == K - 1 and ev[i][1] <= a:
gap = max(gap, a - ev[i][1])
print(K, gap) # 26 11
Проверка. Заявок $990$, жадный подсчёт на том же файле тоже даёт $26$ мероприятий. Перерыв вышел небольшим — $11$ минут: заявки плотные, и на последнем шаге свободы почти не остаётся. На типовом примере из условия программа выдаёт $3$ и $20$.
20
