Задание №26 — Сортировка
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба.
Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные:
В первой строке входного файла находится натуральное число N (N ≤ 1000) –
количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Типовой пример организации данных во входном файле:
5
10 150
100 120
131 170
150 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Правильный ответ
32 15
Пояснение
Решение:
Это классическая задача о расписании: заявки — это отрезки времени, а провести можно только такие мероприятия, отрезки которых не перекрываются. При этом касание разрешено: если одно мероприятие заканчивается ровно в тот момент, когда начинается другое, оба состоятся.
Первую величину — наибольшее число мероприятий — даёт стандартный приём: отсортировать заявки по времени окончания. Но нам нужен ещё и максимальный перерыв между двумя последними мероприятиями, поэтому удобнее не жадный проход, а динамическое программирование по отсортированному списку: пусть dp[i] — наибольшее количество мероприятий в расписании, последним в котором стоит мероприятие i. Тогда dp[i] на единицу больше лучшего dp[j] среди заявок j, которые заканчиваются не позже начала i. Максимум по всем dp[i] и есть искомое количество .
Теперь перерыв. Два последних мероприятия — это пара (j, i), в которой i завершает расписание длины (то есть dp[i] = K), а j предшествует ему в расписании длины (то есть dp[j] = K-1) и заканчивается не позже начала i. Перерыв равен разности «начало i минус конец j»; перебираем все такие пары и берём наибольшую разность.
f = open('26.txt')
n = int(f.readline())
a = []
for i in range(n):
start, end = map(int, f.readline().split())
a.append((end, start)) # сортировать будем по времени окончания
a.sort()
dp = [1] * n
for i in range(n):
for j in range(i):
if a[j][0] <= a[i][1] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
k = max(dp)
gap = 0
for i in range(n):
if dp[i] != k:
continue
for j in range(n):
if dp[j] == k - 1 and a[j][0] <= a[i][1]:
gap = max(gap, a[i][1] - a[j][0])
print(k, gap)
Проверим программу на типовом примере из условия: она выдаёт 3 и 20 — ровно то, что написано в задании. На данных из прилагаемого файла (990 заявок) получаем 32 мероприятия и перерыв 15 минут. Квадратичный перебор здесь допустим: при это около миллиона проверок.
Ответ: 32 15