Навигация по странице
Тип 4
К четвертому типу 26 заданий мы отнесём задания, в которых требуется составить расписание каких-либо мероприятий. Откровенно говоря, задача о составлении расписания является самым базовым примером использования жадных алгоритмов.
Мы уже ранее затрагивали тему с жадными алгоритмами, когда рассматривали первый тип 26 заданий. В тот раз нам необходимо было добиться максимальной вложенности объектов: коробок, коржей и так далее.
В случае же с заданиями на составление расписания от нас требуется определить максимальное количество непересекающихся по времени мероприятий из предложенного списка.
Давайте, как обычно, начнём с абстрактного примера. Представьте, что вы находитесь на научной конференции. На этой конференции работает сразу несколько секций, в которых проходят доклады по интересующим вас темам.
Попасть одновременно на два доклада в двух разных секциях вы никак не можете. Но как же вам максимально эффективно провести день и побывать на максимальном количестве докладов?
Допустим, есть такое абстрактное расписание всех докладов:
Как мы уже поняли, посетить все доклады не получится. Можем продемонстрировать наложение этих докладов на диаграмме Ганта.
Как отобрать доклады таким образом, чтобы полученный набор оказался самым большим из возможных?
Эта на первый взгляд непростая задача на самом деле имеет на удивление простое решение:
- Для начала следует выбрать доклад, завершающийся раньше всех. В нашем случае это доклад под номером 1
- Затем выбирается доклад, время начала которого не раньше времени окончания уже выбранного доклада
- При равенстве времени начала двух докладов следует выбрать тот, который заканчивается раньше
По такому алгоритму сначала мы посетим доклад под номером 1: он закончится в 10:30. В это время еще не начался никакой другой доклад, так что мы можем спокойно подождать начала следующего.
Следующим у нас будет доклад под номером 3: он начнётся в 11:00 и закончится в 13:30. Сразу после его завершения мы можем попасть на последний на сегодня доклад – под номером 5. Продемонстрируем наш выбор на «схлопнувшейся» диаграмме Ганта:
Таким образом, у нас получилось выбрать максимальное количество доступных докладов. Здесь важно понять, что первым следует выбрать именно то мероприятие, которое заканчивается раньше всех. Этим выбором мы оставим как можно больше времени под остальные мероприятия.
В этом и заключается суть жадного алгоритма: на каждом шаге (выборе следующего мероприятия) он выбирает наиболее оптимальный вариант. В нашем примере при выборе доклада выбирается как раз тот, что завершается раньше других.
В технической терминологии: на каждом шаге выбирается локально-оптимальное решение, а в итоге получается глобально-оптимальное решение. И такой простой алгоритм позволяет успешно находить оптимальное решение каждой задачи составления расписания.
Теперь можем смело переходить к решению 26 заданий четвёртого типа. Начнём с такой формулировки:
Задание 2609
«Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Типовой пример организации данных во входном файле
5
10 150
100 120
131 170
150 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5»
Разберём предложенный в условии пример. Сформируем из данных значений таблицу.
Отсортируем данные сначала по возрастанию времени окончания, а затем по убыванию времени начала.
Получаем такую таблицу.
Самое первое мероприятие (с номером 2) нам точно подходит, так что сразу добавляем его в список одобренных.
Теперь рассматриваем следующие мероприятия по списку и проверяем, чтобы их время начала было больше или равно времени окончания последнего взятого мероприятия.
Так, следующим в нашем списке одобренных будет мероприятие под номером 5. А ближайшее после него мероприятие, которое нам подходит, будет под номером 3.
Но здесь стоит отметить важное замечание в условии: «максимально возможный перерыв между двумя последними мероприятиями». Между мероприятиями под пятым и третьим номером перерыв будет всего в 1 минуту.
Но никто нам не запрещает в качестве последнего взять любое другое мероприятие далее по списку. Ведь оно и так будет начинаться не ранее окончания предпоследнего мероприятия из нашего списка одобренных. Например, вместо третьего номера можем взять четвёртый.
И в таком случае максимальный перерыв между предпоследним и последним мероприятиями будет составлять 20 минут.
Значит, всего можно провести три мероприятия, а максимальный перерыв между последними двумя будет 20 минут. Наши ответы сошлись с теми, что представлены в условии, так что можем переходить к решению с реальными данными.
Начинаем со считывания данных из файла. Создаём список data, куда будем помещать словари со значениями из каждой строчки файла. Словарями мы здесь пользуемся для увеличения читаемости кода, вы же можете использовать и обычные списки.
data = []
with open('2609.txt') as file:
N = int(file.readline())
for line in file:
parts = line.strip().split()
event = {
"start": int(parts[0]),
"end" : int(parts[1])}
data.append(event)
Далее идёт сортировка. Как и оговаривалось раньше, сортируем сначала по возрастанию времени окончания, затем по убыванию времени начала.
events = sorted(data, key=lambda event: (event["end"], -event["start"]))
Первое мероприятие нам точно подходит, сразу добавляем его в список с одобренными мероприятиями approved_events:
approved_events = [events[0]]
Теперь в цикле рассматриваем все элементы начиная со второго из списка events и если время начала рассматриваемого мероприятия больше или равно времени окончания последнего из списка approved_events, то добавляем это мероприятие в конец списка approved_events.
for event in events[1:]:
if event["start"] >= approved_events[-1]["end"]:
approved_events.append(event)
Для получения ответа на первый вопрос задания необходимо лишь подсчитать количество элементов в списке approved_events.
Переходим ко второму вопросу: необходимо найти максимально возможный перерыв между двумя последними мероприятиями.
Заводим отдельную переменную longest_break под значение перерыва между последними мероприятиями. Изначально она будет равна нулю.
longest_break = 0
В цикле перебираем все мероприятия из events, но сразу проверяем, что время начала будет больше или равно времени окончания предпоследнего одобренного мероприятия.
То есть таким образом мы начинаем проверку только тех мероприятий, которые расположены после предпоследнего одобренного. Осталось лишь найти максимальную длительность перерыва.
Для этого будем искать наибольшее среди двух значений: текущее значение longest_break и разность между началом рассматриваемого мероприятия и окончанием предпоследнего одобренного.
Получаем такой код:
for event in events:
if event["start"] >= approved_events[-2]["end"]:
longest_break = max(longest_break, event["start"] - approved_events[-2]["end"])
В конце выводим два наших ответа: количество мероприятий и максимально длинный перерыв между последними двумя.
print(len(approved_events), longest_break)
Весь код здесь будет такой:
data = []
with open('2609.txt') as file:
N = int(file.readline())
for line in file:
parts = line.strip().split()
event = {"start": int(parts[0]), "end": int(parts[1])}
data.append(event)
events = sorted(data, key=lambda event: (event["end"], -event["start"]))
approved_events = [events[0]]
for event in events[1:]:
if event["start"] >= approved_events[-1]["end"]:
approved_events.append(event)
longest_break = 0
for event in events:
if event["start"] >= approved_events[-2]["end"]:
longest_break = max(longest_break, event["start"] - approved_events[-2]["end"])
print(len(approved_events), longest_break)
В ответ запишем два числа: 32 и 15.
Пример
Рассмотрим следующее заданий с очень похожей формулировкой:
Задание 2610
«Входной файл содержит сведения о мероприятиях, в которых приглашён участвовать директор фирмы. Для каждого мероприятия указаны время начала и длительность его проведения (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то руководитель может принять участие только в одном из них. Если время окончания одного мероприятия совпадает со временем начала другого, то руководитель может принять участие в обоих мероприятиях (очно и дистанционно). Определите, в каком максимальном количестве мероприятий может принять участие руководитель, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные
В первой строке входного файла находится натуральное число N (N <= 1000) — количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающие время начала и длительность мероприятий. Каждое из чисел натуральное, не превосходящее 1440. Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах)
Типовой пример организации данных во входном файле:
5
20 120
90 20
147 43
150 30
120 20
При таких исходных данных можно провести максимум 3 мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 10 мин., если состоятся мероприятия по заявкам 2, 4 и 5»
Сразу отметим, что вторым значением в строке здесь является длительность мероприятия, а не время его окончания. Но ничего страшного, зная время начала и длительность, мы запросто можем высчитать время окончания.
Считаем данные из файла.
data = []
with open('2610.txt') as file:
N = int(file.readline())
for line in file:
parts = line.strip().split()
end = int(parts[0])+int(parts[1])
event = {"start": int(parts[0]), "end": end}
data.append(event)
Обратите внимание, что второе значение в словаре здесь высчитывается, а не извлекается из файла!
Больше отличий от предыдущего кода здесь не будет. Полное решение выглядит следующим образом:
data = []
with open('2610.txt') as file:
N = int(file.readline())
for line in file:
parts = line.strip().split()
end = int(parts[0])+int(parts[1])
event = {"start": int(parts[0]), "end": end}
data.append(event)
events = sorted(data, key=lambda event: (event["end"], -event["start"]))
approved_events = [events[0]]
for event in events[1:]:
if event["start"] >= approved_events[-1]["end"]:
approved_events.append(event)
longest_break = 0
for event in events:
if event["start"] >= approved_events[-2]["end"]:
longest_break= max(longest_break, event["start"] - approved_events[-2]["end"])
print(len(approved_events), longest_break)
В результате работы нашей программы получаем два числа: 26 и 20, которые и записываем в ответ.