26. Прикладная задача: Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру…
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение $1$ мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение $24$ ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.
Это прямое моделирование, никакой оптимизации искать не нужно. Заявки в файле лежат вперемешку, поэтому первым делом сортируем их по времени сдачи багажа — обслуживать пассажиров надо в порядке их прихода.
Для каждой ячейки храним одно число: момент, когда она освобождается. Пассажир с временем прихода $t$ может занять ячейку, если она освободилась строго раньше, то есть если записанное для неё время меньше $t$. Это ровно та формулировка «начиная со следующей минуты» из условия: ячейка, освобождённая в минуту $60$, доступна с минуты $61$.
Перебираем ячейки по возрастанию номера и берём первую подходящую — так выполняется требование про минимальный номер. Если подходящей нет, пассажир уходит. Попутно считаем успешных пассажиров и запоминаем, кто занял ячейку последним по времени; при совпадении времени берём меньший номер ячейки.
f = open('26-07.txt')
K = int(f.readline())
N = int(f.readline())
req = [tuple(map(int, f.readline().split())) for _ in range(N)]
req.sort() # по времени сдачи багажа
free = [0] * K # время, когда ячейка освободится
cnt = 0
last_t, last_cell = -1, None
for t, e in req:
for i in range(K):
if free[i] < t: # доступна со следующей минуты
free[i] = e
cnt += 1
if t > last_t:
last_t, last_cell = t, i + 1
elif t == last_t and i + 1 < last_cell:
last_cell = i + 1
break
print(cnt, last_cell) # 368 83
Проверка. Ячеек $210$, заявок $987$, успешными оказались $368$ пассажиров. Последняя сдача багажа среди них произошла на $997$-й минуте, и в этот момент был всего один такой пассажир — он занял ячейку $83$. На типовом примере из условия программа выдаёт $4$ и $1$.