Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

26. Прикладная задача: Входной файл содержит сведения о заявках на проведение мероприятий в…

Задание #298053
Решено верно
Решено неверно
Сообщить о проблеме

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

Входные данные

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

Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).

Типовой пример организации данных во входном файле:

5
10 150
100 120
131 170
150 180
120 130

При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам $2$, $3$ и $5$. Максимальный перерыв между двумя последними мероприятиями составит $20$ мин., если состоятся мероприятия по заявкам $2$, $4$ и $5$.

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

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

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

f = open('26-14-2.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)   # 23 19

Проверка. Заявок $990$, жадный подсчёт на том же файле тоже даёт $23$ мероприятия. На типовом примере из условия программа выдаёт $3$ и $20$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение