26. Прикладная задача: Входной файл содержит информацию о заявках граждан, обращающихся во…
Входной файл содержит информацию о заявках граждан, обращающихся во многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом (в минутах от начала суток). Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с $1$. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит. Определите, сколько граждан смогут попасть на приём в МФЦ в течение $24$ ч, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.
Заявки в файле лежат вперемешку, поэтому сначала сортируем их по времени начала приёма — обслуживать граждан надо в порядке обращения. Для каждого окна храним одно число: момент, когда специалист освободится. Гражданин с временем обращения $t$ может попасть в окно, если это число меньше $t$ — так реализуется правило «начиная со следующей минуты после завершения приёма предыдущего».
Перебираем окна по возрастанию номера и берём первое подходящее, что и даёт требуемый минимальный номер. Если подходящего нет, гражданин уходит. Попутно считаем принятых и запоминаем, кто обратился последним по времени; при совпадении времени берём меньший номер окна.
f = open('26-17.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_win = -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_win = t, i + 1
elif t == last_t and i + 1 < last_win:
last_win = i + 1
break
print(cnt, last_win) # 793 2
Проверка. Окон $267$, заявок $994$, на приём попали $793$ гражданина. Последнее обращение среди них произошло на $1437$-й минуте, и такой гражданин был один — его принял специалист в окне $2$. На типовом примере из условия программа выдаёт $4$ и $1$.