Задача типа #26: Обработка данных с помощью сортировки
Обработка данных с помощью сортировки
Входной файл содержит заявки на печать на 3D-принтере в течение одних суток.
Каждая заявка задаётся двумя числами — временем начала и временем окончания печати в минутах от начала суток (0–1440).
Если время печати двух или более заявок пересекается, то выполнить можно только одну из них.
Между окончанием одной печати и началом следующей должен быть перерыв не менее 2 минут — для охлаждения и подготовки принтера к следующему заданию.
Какое максимальное количество печатей можно выполнить в этот день?
Каким при этом может быть максимально возможный перерыв между двумя последними печатями?
В ответе запишите два числа - максимальное количество печатей и максимально возможный перерыв между двумя последними печатями.
Файл содержит данные о заявках на печать. Каждая строка содержит данные одной заявки - два натуральных числа (время начала и время окончания печати)
Алгоритм решения: Считываем данные всех заявки с временем начала и окончания. Сортируем заявки по времени окончания по возрастанию (‘жадный’ алгоритм). Перебираем заявки, берем заявку, если она начинается после окончания предыдущей. Запоминаем время окончания текущей заявки + 2 минуты на перерыв. Заменяем последнюю заявку в ‘жадном’ списке на последнюю существующую заявку - находим наибольший возможный перерыв.
Посмотреть решение задачи (код на Python) в Telegram боте по ID задачи 126014