В городе открылось кафе. В нем есть К столиков. После каждого клиента столик необходимо убрать, на это уходит 12 минут. Из-за большой загруженности, уборка начинается через 5 минут после того, как уходит гость. Новый клиент может сесть через 5 минут после завершения уборки. Кафе работает с 7:00 и закрывается в 20:00. Все клиенты должны уйти не позже 20:00. За это время в него приходит N клиентов. (Гарантируется, что они придут не раньше 7:00, а планируют уйти не позже 20:00).
Каждого гостя при входе встречает администратор и подбирает для него стол с минимальным номером. Может случиться так, что несколько людей придет одновременно, тогда администратор в первую очередь подбирает столик для того, кто планирует сидеть меньшее время. В случае если все столы заняты, гость готов подождать не более 3 минут, при этом за столом он пробудет обязательно T минут (T – разница между временем прибытия и отбытия), в этом случае выбирается столик, который освободится раньше всего. Если таких несколько, выбирается с меньшим номером.
Определите, сколько клиентов получится обслужить за время работы кафе и номер столика, за который сядет последний клиент.
Входные данные. На первой строке одно число N – количество гостей, пришедших за день. На второй строке одно число K – количество столиков в кафе. Далее N строк, в каждой из которых указано время, когда клиент пришел и время, до которого он планировал пробыть в кафе (время дано в минутах от начала дня).
Решение (Python)
f = open(’26_12__30v1f.txt’)
n = int(f.readline()) # считываем количество пришедших клиентов
k = int(f.readline()) # считываем количество мест в кафе
clients = [] # список клиентов
for line in f.readlines():
a, b = map(int, line.split())
clients.append([a, b])
clients.sort() # сортируем список клиентов
table = [-1] * k # список, симулирующий каждое рабочее место, в котором будет записано время, в которое освободится каждое место
ans1 = 0
ans2 = 0
for client in clients: # проход по каждому клиенту
ok = False # флаг, которые показывает нужно ли человеку ждать или нет
for i in range(k):
# если время прихода текущего клиента больше чем время освобождения данного места другим клиентом
if client[0] >= table[i]:
table[i] = client[1] + 22 # записываем время ухода текущего клиента с учётом уборки данного места после него
ok = True # помечаем, что для текущего клиента нашли место
ans1 += 1 # увеличиваем счётчик пришедших клиентов
ans2 = i + 1 # запоминаем номер места, куда сел последний клиент
break # прерываем цикл - переходим к следующему клиенту
if not ok: # если клиенту нужно подождать
mt = min(table) # определяем место, которое освободится в ближайшее время
if client[0] + 3 >= mt: # если время ожидания не более 3 минут
ind = table.index(mt) # определяем индекс данного места в списке
T = client[1] - client[0] # считаем время T
if table[ind] + T <= 1200: # если данный клиент уйдёт не позже закрытия
table[ind] += T + 22 # то сажаем данного человека за место
ans1 += 1 # увеличиваем счётчик пришедших клиентов
ans2 = ind + 1 # запоминаем номер места, куда сел последний клиент
print(ans1, ans2)