Задание 26 ЕГЭ: жадный выбор интервалов

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

Пример

Задание выполняется с использованием прилагаемого файла.

На зарядную станцию для электромобилей поступили заявки на сеансы зарядки. Для каждой заявки известны время начала сеанса (в минутах от начала суток) и его длительность в минутах. У станции один разъём, поэтому одновременно может проходить только один сеанс; сеанс длится с момента начала до момента окончания. Если время окончания одного сеанса совпадает со временем начала другого, провести можно оба.

Определите максимальное количество сеансов, которые может провести станция, и самое раннее время, к которому она может закончить это максимальное количество сеансов (время окончания последнего сеанса).

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

Первая строка входного файла 26.txt содержит два целых числа: N — количество заявок и P — минимальный перерыв между сеансами в минутах. Каждая из следующих N строк содержит два натуральных числа: время начала сеанса и его длительность в минутах; все сеансы заканчиваются не позже 1440-й минуты.

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

Два числа: сначала максимальное количество сеансов, затем самое раннее время окончания последнего сеанса.

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

5 0
60 60
100 80
130 70
200 100
190 70

При таких исходных данных можно провести 3 сеанса, раньше всего станция закончит их к 300-й минуте. Ответ для примера: 3 300.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Запишите два числа через пробел.

Скачать файл к примеру

Решение

Классическая жадность: сортируем заявки по времени окончания и берём очередную, если она начинается не раньше, чем через P минут после окончания последней взятой. Так получается наибольшее количество сеансов, причём каждый k-й выбранный сеанс заканчивается не позже k-го сеанса любого другого допустимого набора — значит, и последний сеанс жадного набора заканчивается раньше всех.

Ответ: 78 1385.

f = open("26.txt")
n, P = map(int, f.readline().split())
a = []
for _ in range(n):
    s, d = map(int, f.readline().split())
    a.append((s, s + d))

ends = []                                 # концы жадно выбранных заявок
for s, e in sorted(a, key=lambda t: t[1]):
    if not ends or s >= ends[-1] + P:
        ends.append(e)
k = len(ends)
print(k, ends[-1])                        # жадность заканчивает раньше всех

Решить такую задачу — новый вариант с проверкой