На вокзале есть А камер хранения для пассажиров, которые пронумерованы с 1. Приходя на вокзал, пассажир кладет свои вещи в свободную камеру с минимальным номером. Известно время, когда пассажиры сдают и забирают вещи (в минутах с начала суток). Камера доступна для багажа начиная со следующей минуты после окончания срока хранения. В случае, когда свободных камер не находится, багаж не принимается и пассажир уходит.
Найдите количество пассажиров, которые сдадут свой багаж в камеры за 24 часа и номер камеры, в которую сдаст багаж последний пассажир.
Входные данные. В первой строке входного файла находится число A – количество камер хранения, во второй строке файла число B – количество пассажиров, сдающих багаж (натуральное число, не превышающее 1000). Каждая из следующих B строк содержит два натуральных числа, не превышающих 1600: время сдачи багажа и время выдачи багажа.
Выходные данные. Программа должна вывести два числа через пробел: число пассажиров, которые сдадут свой багаж в камеры и номер камеры, в которую примут вещи у последнего пассажира.
Решение (Python)
f = open(’26_3__1vv31.txt’)
k = int(f.readline()) # количество камер хранения
n = int(f.readline()) # количество пассажиров, сдающих багаж
# Создаём список, в котором будут храниться данные о времени,
# когда каждый пассажир собирается сдавать и забирать вещи
a = []
for i in range(n):
st, end = map(int, f.readline().split())
a.append([st,end])
# Применяем сортировку, чтобы пассажиры приходили в том порядке, который задан временем их прихода
a.sort()
count = 0 # Кол-во пассажиров, сдавших багаж
last = 0 # Номер камеры, в которую примут вещи у последнего пассажира
# Список с данными о каждой камере
kamera = [[0,0]]*k
# Перебор пассажиров
for i in range(n):
# Проходимся по каждой камере
for j in range(k):
# Если из текущей камеры багаж заберут раньше,
# чем придёт пассажир, то помещаем багаж пассажира в эту камеру
if kamera[j][1] < a[i][0]:
kamera[j] = a[i]
count += 1
# Сохраняем номер последней ячейки
# (прибавляем единицу, так как нумерация мастеров с единицы, а не с нуля)
last = j+1
# Прерываем внутренний цикл, чтобы перейти к следующему пассажиру
break
print(count, last)