Задание №26. Сортировка и выбор объектов

В задании №26 файл содержит сведения о множестве объектов: мероприятиях, грузах, местах или запросах. Требуется выбрать подходящий набор либо воспроизвести правила обработки данных. Сортировка помогает увидеть нужный порядок, но сама по себе ещё не даёт решения. Важно установить, что ограничивает выбор, какая величина должна стать наибольшей или наименьшей и что требуется при равенстве основных результатов.

Что означает одна запись

Запись содержит сведения об одном объекте. Пара чисел может означать начало и конец мероприятия, ряд и место или размер и материал коробки. Эти поля нельзя переставлять без изменения смысла. Первая строка файла обычно задаёт количество записей и дополнительные параметры; она читается отдельно от самих объектов.

Критерий определяет, какой допустимый результат лучше. В условии могут быть два последовательных критерия: сначала максимальное количество объектов, затем наибольшая величина среди наборов с этим количеством. Второй критерий не разрешает уменьшать первый. Кроме того, два числа ответа не всегда являются двумя целями: номер клиента и объём резервных копий могут вычисляться независимо.

Мероприятия: максимум количества и позднейшее окончание

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

Почему выбирается раннее окончание

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

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

Пять заявок из иллюстрации условия

Ниже приведён именно маленький пример из условия. Это не первые строки полного входного файла.

По возрастанию конца заявки идут в порядке 2,5,1,3,4. Сначала выбирается заявка 2, зал занят до минуты 110. Заявка 5 начинается в 120, поэтому тоже выбирается; теперь конец равен 130. Заявка 1 начинается раньше этого времени и пропускается. Затем выбирается заявка 3, а заявка 4 уже пересекается с ней. Получены три мероприятия.

Однако конец 170 ещё не отвечает второму требованию. Начальная часть расписания из первых двух мероприятий заканчивается в 130. Среди заявок с началом не раньше этой минуты наибольший конец равен 180. Замена последней заявки на четвёртую сохраняет три мероприятия. Ответ иллюстрации: 3\quad180.

Почему достаточно заменить последнюю заявку

Пусть максимум количества равен k. Выбранные по раннему окончанию первые k-1 мероприятий заканчиваются не позже любой другой допустимой последовательности такой длины. Это следует из той же последовательной замены. Поэтому последняя заявка любого расписания из k мероприятий совместима и с этой начальной частью. Просмотр всех заявок, начинающихся после неё или в момент её окончания, не теряет ни одного возможного позднего конца.

Состояния chosen, finish, prefix и latest прослежены в статье «Как работает программа отбора мероприятий». Она связывает каждую ветку программы с принятым или пропущенным мероприятием.

Программа для полного файла

Архив задания содержит файл 2_26.txt. В первой строке записано количество заявок; далее читается ровно столько пар. Функция end_time возвращает конец заявки, по которому sort упорядочивает список. В chosen сохраняются времена окончания выбранных мероприятий.

with open("2_26.txt") as f:
    n = int(f.readline())
    events = []
    for _ in range(n):
        row = f.readline()
        pair = map(
            int, row.split()
        )
        events.append(
            tuple(pair)
        )

def end_time(event):
    return event[1]

events.sort(key=end_time)
chosen = []
finish = 0
for start, end in events:
    if start >= finish:
        chosen.append(end)
        finish = end

prefix = 0
if len(chosen) >= 2:
    prefix = chosen[-2]

latest = 0
for start, end in events:
    if start >= prefix:
        latest = max(
            latest, end
        )

print(len(chosen), latest)

После первого прохода finish хранит конец последнего выбранного мероприятия. Условие start >= finish разрешает стык без перерыва. Во втором проходе prefix равен концу предпоследнего выбранного мероприятия. Если выбрано только одно, начальная часть пуста и границей остаётся ноль.

В полном файле 990 заявок. Первый проход выбирает 53 мероприятия. Первые 52 заканчиваются в минуту 1020; последнее в первоначальном выборе идёт с 1023 до 1057. Второй проход находит заявку с 1026 до 1300. Она совместима с сохранённой начальной частью и даёт ответ 53\quad1300. Второе число обозначает минуты от начала суток, не длительность мероприятия.

В задаче о максимальном перерыве ↗ первый критерий тот же, но второй другой. После первых k-1 мероприятий ищется самое позднее начало допустимого последнего. Из него вычитается конец предпоследнего. Минимальный конец начальной части оставляет все варианты последнего и увеличивает перерыв. Для полного файла этой задачи ответ равен 25\quad16: мероприятия и минуты перерыва.

Размеры и вместимость

Коробки внутри коробок

В упаковке без ограничения на материал ↗ соседние размеры различаются хотя бы на 9. Размеры сортируются по убыванию. После самой большой коробки берётся самая большая из помещающихся, затем правило повторяется. Замена очередной коробки на более крупную допустимую сохраняет все меньшие коробки внутри неё. Поэтому выбор не уменьшает максимальное количество и на каждом шаге сохраняет максимально возможный размер. Последний выбранный размер максимален среди самых маленьких коробок цепочек наибольшей длины. Ответ полного файла: 1040\quad57. В иллюстрации условия зазор другой, 3; переносить его в решение полного файла нельзя.

В коробках двух материалов ↗ соседние материалы должны различаться. Теперь более крупная коробка другого материала может запретить следующее вложение. Учебный контрпример, не данные файла: при зазоре 3 имеются пары размер–материал (9,0),(8,1),(5,0),(2,1). Начало с девяти даёт только 9\to2, а цепочка 8\to5\to2 содержит три коробки.

Здесь подходит динамическое программирование. Размеры обрабатываются от больших к меньшим. Пусть D обозначает минимальный зазор. Для коробки размера s и материала m длина лучшей цепочки, заканчивающейся ею, равна единице плюс лучшая длина среди внешних коробок другого материала размером хотя бы s+D. Если внешней коробки нет, длина равна единице.

Два массива лучших длин по порогу размера позволяют получать этот максимум без просмотра всех пар коробок. Среди коробок, завершающих цепочку наибольшей длины, выбирается наибольший размер. В полном файле D=57, ответ 166\quad63. Устройство массивов поясняется в статье "Сортировка и обоснование выбора".

Общая масса и отдельные контейнеры

При одной общей грузоподъёмности ↗ сначала берутся массы по возрастанию, пока их сумма помещается. Любые другие столько же грузов весят не меньше, поэтому следующий не поместившийся минимальный груз доказывает невозможность увеличить количество. Для второго критерия сохраняются первые k-1 самых лёгких грузов, а последним выбирается самый тяжёлый из оставшихся, помещающийся в остаток грузоподъёмности. Минимальная сумма сохранённых грузов оставляет ему максимально возможный запас. Ответ полного файла: 1612\quad90.

В распределении по отдельным контейнерам ↗ каждый контейнер вмещает только один груз. Складывать грузоподъёмности нельзя. Контейнеры рассматриваются от самого вместительного к меньшим; каждому назначается самый тяжёлый из ещё не назначенных грузов, который помещается. Слишком тяжёлые грузы пропускаются: в оставшиеся меньшие контейнеры они тоже не войдут.

Если выбранный груз в другом оптимальном распределении лежит в меньшем контейнере, его можно обменять с грузом текущего: более лёгкий поместится на освободившееся место. Если выбранный груз вообще не использован, он заменяет текущий без потери количества. Такой обмен обосновывает выбор и сохраняет самый тяжёлый доступный груз. Ответ: 791\quad197491. Максимальная масса во всём файле сама по себе не является ответом: груз должен помещаться.

Рейтинг и буквальное выполнение правил

В учёте товаров ↗ сначала вычисляется средняя цена по всем единицам, включая проданные и оставшиеся. Затем записи объединяются по артикулу: подсчитываются продажи и остаток. Среди товаров строго дороже среднего сравниваются количество продаж по убыванию, цена по убыванию и остаток по возрастанию. Следующее поле используется только при равенстве предыдущих. У лидера полного файла продана 51 единица по цене 856, поэтому выручка 51\cdot856=43656; остаток равен 36.

В рейтинге студентов ↗ сначала отделяются сдавшие сессию, затем сортируются по среднему баллу вниз и ID вверх. У всех четыре экзамена, поэтому сравнение сумм даёт тот же порядок, что сравнение средних. Несдавшие располагаются по количеству двоек вверх, затем по ID вверх. Последний получатель повышенной стипендии занимает позицию N/4, то есть индекс N // 4 - 1 в списке Python. Первый студент с более чем двумя двойками ищется в своей группе; результаты этих двух поисков не подменяют друг друга.

В рейтинге продуктов с заполнением с двух концов ↗ правило уже дано. Каждому из двух сроков приписываются номер продукта и вид срока; все сроки сортируются вместе. Ещё не размещённый продукт ставится на первое свободное место слева либо справа по виду встретившегося срока. Второе появление того же продукта пропускается. Последний обработанный продукт не обязательно стоит последним в готовом рейтинге: число более высоких мест определяется его итоговой позицией.

Свободные места: важна ось группировки

В поиске двух свободных мест между занятыми ↗ записи объединяются по ряду, занятые места внутри ряда сортируются. Если соседние занятые номера равны a и b, между ними b-a-1 свободных мест. Требуются ровно два, значит b-a=3; первый свободный номер равен a+1. Из подходящих выбирается максимальный ряд, а в нём минимальный первый номер. Более широкий промежуток не подходит: выбранная пара не будет ограничена занятыми с обеих сторон.

В поиске свободных кресел перед выбранным ↗ группировать нужно по номеру кресла, а сортировать номера занятых рядов. Между занятыми рядами a и b, если там есть свободное кресло, последнее из них находится в ряду b-1. Перед ним свободны b-a-2 кресла подряд. Само покупаемое кресло в этот счёт не входит. Пусть всего в зале M рядов. Для краёв используются условные границы 0 и M+1; полностью свободный номер кресла имеет только эти границы. Среди максимальных просветов выбирается ближайший к сцене ряд.

Для двух соседних кресел со свободным пространством до сцены ↗ у каждого номера достаточно найти первый занятый ряд. Для соседних номеров последний допустимый ряд на единицу меньше минимума этих двух границ. При отсутствии занятых мест граница равна M+1. Максимизируется ряд, затем выбирается меньший номер подходящей пары. В другом условии может требоваться больший номер той же пары: формат ответа читается отдельно.

События и состояние памяти

В задачах обслуживания записи обрабатываются по времени, а после каждой обновляется состояние: занятость окон, объём памяти, число обслуженных клиентов. Граница освобождения берётся из условия. В учебном примере ресурс занят до минуты 60, новая заявка начинается в 60. При разрешённом стыке она подходит; при доступности только со следующей минуты не подходит, нужно строгое start > end.

Если события представлены отдельными началами и окончаниями, при разрешённом стыке освобождение обрабатывается раньше нового занятия в тот же момент. При запрете стыка порядок обратный. Для одновременных приходов также нужен порядок из условия, если от него зависит назначение. При требовании минимального номера свободного окна выбирается именно этот номер, а не окно, которое освободилось раньше всех.

В журнале сервера ↗ отдельно суммируются данные каждого клиента и моделируется память в порядке времени. Пусть u уже занято, s занимает новый запрос, K обозначает вместимость. При u+s>K сначала создаётся копия объёма u, память очищается, затем добавляется запрос. При точном равенстве копии ещё нет. Время копии равно времени запроса, вызвавшего переполнение.

После конца журнала остаток не превращается в копию автоматически. Для этой задачи из копий, созданных не позднее 11{:}59{:}59, выбираются две наибольшие и складываются; суммы клиентов считаются за весь журнал. В полном файле ответ 7040\quad52204: ID клиента и Кбайт. Перенос временного фильтра с копий на клиентов изменил бы первый результат.

Возможные ловушки

• Вывести конец первоначального жадного расписания. В задаче о позднем окончании ↗ ранний конец нужен для максимума количества. После него требуется отдельный выбор последней заявки; иначе второй критерий остаётся нерешённым.
• Считать одинаковые размеры одним объектом. Повторяющиеся массы в перевозке контейнеров ↗ принадлежат разным контейнерам. Превращение списка в множество уменьшит количество доступных объектов.
• Усреднить цены артикулов. В учёте товаров ↗ среднее считается по единицам. Артикул с десятью единицами участвует десять раз, независимо от статуса продажи.
• Добавить новый запрос перед копированием. В журнале сервера ↗ он ещё не помещается, поэтому не входит в создаваемую копию. Правильный порядок: сохранить прежний объём, очистить память, добавить запрос.