В салоне красоты работают A количество мастеров. У каждого человека есть свой номер, начиная с единицы. Директору салона нужно записать B клиентов на следующий день. Порядок записи следующий: клиент звонит в салон и называет время в которое каждый клиент хочет прийти в салон, и в какое время он хочет завершить прием. Директор записывает клиента к мастеру с наименьшим номером, который свободен в тот промежуток, который нужен клиенту. Мастера могут принимать клиентов со следующей минуты после предыдущего клиента. Если таких мастеров нет, то директор сразу во время звонка просит прощения у клиента и сообщает, что он не может записать его.
Длительность рабочего дня салона составляет 600 минут.
Определите сколько клиентов смог записать директор и номер мастера, к которому записался последний клиент.
Входные данные. В первой строке входного файла находится число А – количество мастеров в салоне (натуральное число, не превышающее 1000). Во второй строке находится число В – количество клиентов, которые хотят записаться. В следующих В строках находятся два значения: минута с которой клиент хочет записаться и минута, до которой клиент планирует записаться, отсчёт ведётся от начала рабочего дня салона (все числа положительные, не превышающие 600), для каждого клиента – в отдельной строке. Данные в файле даны в том порядке, в котором клиенты звонили в салон.
Запишите в ответе два целых числа через пробел: сначала количество клиентов, которое сможет записать директор, затем номер мастера, к которому записался последний клиент.
f = open(’26_5.txt’)
k = int(f.readline()) # Кол-во мастеров
n = int(f.readline()) # Кол-во клиентов
# Список с записями клиентов по времени
times=[list(map(int, f.readline().split())) for _ in range(n)]
# Массив, в который будут по порядку заноситься номера мастеров
clients = []
# Список с графиком времени каждого специалиста
# Единицей будут помечаться занятые минуты мастера
specialists=[[0]*601 for _ in range(k)]
for start, end in times:
# Пробегаемся по каждому специалисту,
# если график свободен для клиента, то добавляем его
for num in range(k):
if sum(specialists[num][start:end+1])==0:
# Добавляем в список номер мастера, к которому обратился клиент
# (прибавляем единицу, так как нумерация мастеров с единицы, а не с нуля)
clients.append(num+1)
# Помечаем занятый период в графике мастера
for time in range(start, end+1):
specialists[num][time]=1
# Прерываем перебор, так как текущий клиент занял место у мастера
break
# len(clients) — сколько раз клиенты обращались к мастерам
# clients[-1] — номер последнего мастера, к которому обратились
print(len(clients), clients[-1])