В отеле составляют недельный план уборки номеров после отъезда клиентов. Все номера одинаковые и пронумерованы с 1 до К. В основе плана журнал заявок, в каждой из которых записано время заезда и время выезда для N заявок. Заявки поступают в случайном порядке. На начало недели все номера подготовлены к заселению.
После отъезда клиента на уборку номера отводится 45 минут. Уборка начинается в следующую минуту после освобождения номера. Клиент может заезжать в подготовленный номер в следующую минуту после уборки. Если подготовленных номеров несколько, то выбирается номер с максимальным временем простоя. Если время простоя одинаковое, то в последний номер. Если подготовленных номеров нет, клиент ждет первый подготовленный номер. При этом время отъезда не меняется.
Найти максимальное время ожидания клиента перед заселением и последний заселенный на планируемой неделе номер. Из-за ожидания заселение может произойти на следующей неделе, что будет учитывается в планах следующей недели. Числа в ответе запишите через пробел.
Входные данные: На первой строке одно число K – количество номеров. На второй строке одно число N – количество заявок. Далее N строк, в каждой из которых указано время заезда и время выезда в минутах, начиная с 0:00 воскресенья.
# k – количество номеров
# n – количество заявок
# data — список со всеми данными
f = open(’C:/26_10.txt’)
k = int(f.readline())
n = int(f.readline())
data = [list(map(int, f.readline().split())) for i in range(n)]
data.sort()
freeTime = [0] * k # время готовности каждого номера
maxWait = 0 # максимальное время ожидания клиента перед заселением
lastRoom = -1 # последний заселенный на планируемой неделе номер
for start, end in data:
rn = 0 # для номера с макс. простоем
for i in range(1, k):
# Если из этого номера выехали раньше, чем из остальных,
# то сохраняем его
if freeTime[i] <= freeTime[rn]:
rn = i
# Расчёт максимального времени ожидания клиента перед заселением.
# Если получится так, что к приезду клиента не будет свободного номера,
# то он может заселиться в номер, который освободится раньше через какое-то время.
# Здесь мы это время и рассчитываем.
# Если доступный номер будет,
# то разность будет отрицательной, значение maxWait так и останется 0
maxWait = max(freeTime[rn] - start, maxWait)
# Если в номер можно заселиться и проживание будет на этой неделе,
# то сохраняем номер. Также сохраняем в списке значение выезда из номера.
if freeTime[rn] <= end and freeTime[rn] < 7*24*60:
freeTime[rn] = end + 46
lastRoom = rn + 1
print(maxWait, lastRoom)