В детском центре есть K аттракционов. Все аттракционы пронумерованы, начиная с 1. Известно время, в которое каждый ребенок хочет начать свою поездку на аттракционе, и в какое время он закончит кататься на нём. Если на аттракционе никто не катается, он считается свободным. Каждый ребенок выбрает свободный аттракцион, который имеет наименьший номер. Если в момент прихода ребенка все аттракционы заняты, то ребенок уходит, не дожидаясь освобождения одного из них. Если некоторые дети придут в парк одновременно, они будут кататься на одном и том же аттракционе вместе. Для того, чтобы остановить и запустить аттракцион заново, необходимо 1 минута. Со следующей минуты следующие дети могут воспользоваться аттракционом. Каждый ребенок за весь день может покататься только на одном аттракционе.
Определите, наибольшее количество детей, которые придут в парк и покатаются на аттракционах за 24 часа и номер аттракциона, который займут последним.
Входные данные. В первой строке входного файла находится два числа K – количество аттракционов в парке развлечений и N – количество детей, которые придут в этот парк (натуральные числа, не превышающее 2000). В следующих N строках находятся два значения: минута прихода и минута, не раньше которой ребенок закончит кататься на аттракционе, отсчёт ведётся от начала суток (все числа неотрицательные, не превышающие 1600), для каждого ребенка – в отдельной строке.
Запишите в ответе два целых числа через пробел: сначала количество детей, которое сможет воспользоваться аттракционами в парке развлечений за 24 часа, затем номер аттракциона, на котором прокатится последний ребенок.
Решение (Python)
f = open(’26_11__1vv3b.txt’)
k, n = map(int,f.readline().split())
a = sorted([list(map(int, i.split())) for i in f])
# переменная для подсчета количества человек
count = 0
lt = 0
# переменная которая хранит время запуска определенного атракциона
d_s = [-1]*k
# переменная которая хранит время остановки определенного атракциона
d_e = [-1]*k
# цикл по людям
for x in a:
start,end = x
# цикл по аттракционам
for j in range(k):
# если время запуска больше времени останова прошлого раза
# или если время запуска равно, так как 2 (и более) человека могут кататься на одном аттракционе одновременно
if start > d_e[j] or (start == d_s[j]):
# прибавляем колчество прокатившихся, обновляем переменные конца и начала
count+=1
d_s[j] = start
d_e[j] = end
lt = j+1
# останавливаем цикл, так как для этого человека уже найден аттракцион
break
print(count,lt)