Входной файл содержит сведения о заявках на проведение...

Задание:

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

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

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

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

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

5
10 150
100 120
131 170
150 180
120 130

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

Примечание: файлы в архиве с демоверсией ЕГЭ-2024 по информатике

Решение (программное)

Рассуждение мы можем построить двумя способами – с конца дня и с его начала. Для построения рассуждения от начала дня зададимся вопросом «Какое мероприятие выгоднее всего провести первым?»

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

Для обработки мероприятий от окончания дня будем работать с вопросом «Какое мероприятие выгоднее всего провести последним?».

Так как нам необходимо помимо количества мероприятий найти максимальную разницу по времени между окончанием предпоследнего мероприятия и началом последнего, то нам необходимо найти самое раннее время, когда окончится предпоследнее мероприятие и самое позднее время, когда мероприятие может начаться. Последнее можно найти без учета распределения мероприятий до него.

Поэтому находить количество мероприятий будем, отвечая на вопрос «Какое мероприятие выгоднее всего провести первым?». Поэтому перед обработкой списка мероприятий отсортируем их по времени их окончания, и будем накапливать новые список, в который будем записывать первые, встреченные в отсортированном списке, мероприятия, начинающиеся позже последнего добавленного в список мероприятия. Изначально в списке будет находиться первый элемент отсортированного списка.

# считываем данные
with open('26_2024.txt') as f:
  n = int(f.readline())
  events = []
  for _ in range(n):
       st, fn = map(int, f.readline().split())
       events.append([st, fn])
             
events.sort(key=lambda x: x[1])

# накапливаем список мероприятий
res = [events[0][1]]
for st, fn in events:
   if st >= res[-1]:
      res.append(fn)

# находим начало самого позднего мероприятия
mx_st = max(events)[0]

# разницу находим, как разность окончания предпоследнего
# и начала самого позднего мероприятия
print(len(res), mx_st - res[-2])

Вывод:
32 15

Решение (электронные таблицы)

Отсортируем данные по значению окончания мероприятия. В качестве окончания первого мероприятия определим значение в первой строке.

Если в одной из следующих строк находится значение начала мероприятия больше завершения последнего, то в столбец С определяем значение его завершения.

C2 =ЕСЛИ(A1>C1; B2; C1)

Для подсчета количества мероприятий найдем все строки, значения в которых в столбце С сменяются. В этих строках увеличим счетчик на 1, начальное значение в первой строке зададим равным 1.

D2 =ЕСЛИ(C1<>C2;D1+1;D1)

Количество мероприятий будет равно максимальному значению в столбце D

F1 =МАКС(D:D)

Найдем время завершения предпоследнего мероприятия. Для этого найдем соответствующую строку.

E2 =ЕСЛИ(И(D2=$F$1-1;C2<>C1);B2; "")

И вычтем из максимального значения в столбце А значение в столбце E (максимальное или минимальное, не важно, оно одно).

F2 =МАКС(A:A) – МАКС(E:E)

Источник: Информатика с Джобсом | ЕГЭ