Решение: Камера хранения
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки в минутах от начала суток. Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.
В первой строке входного файла находится натуральное число K, не превышающее 1000, — количество ячеек в камере хранения. Во второй строке находится натуральное число N (N ≤ 1000), обозначающее количество пассажиров. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: время размещения багажа в ячейке и время освобождения ячейки. Используйте данные из прилагаемого файла.
Решение по шагам
4 шагаСчитать количество ячеек K и количество заявок N. Для каждой ячейки сохранить время, с которого она свободна; изначально все ячейки свободны.
Для каждой заявки с временем сдачи t и временем освобождения e просмотреть ячейки от первой к последней и выбрать первую ячейку, для которой её время доступности не позже t.
$$free_i \le t$$Если подходящая ячейка найдена, увеличить счётчик обслуженных пассажиров и установить для неё время следующей доступности e + 1.
$$free_i := e + 1$$Запомнить наибольший номер ячейки, занятой принятой заявкой. По данным прилагаемого файла вывести количество обслуженных пассажиров и этот номер.
Определяется по данным прилагаемого входного файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Освобождать ячейку в ту же минуту, в которую её можно занять.
Выбирать не первую свободную ячейку, а ячейку с минимальным временем освобождения.
Продолжать обработку заявки после того, как свободная ячейка не найдена.
Забывать учитывать номер последней занятой ячейки, если несколько ячеек имеют одинаковый статус.