В аэропорту есть камера хранения из K ячеек, которые пронумерованы
Принимаемый багаж кладется в свободную ячейку с минимальным номером. Известно время, когда пассажиры сдают и забирают багаж (в минутах с начала суток). Ячейка доступна для багажа, начиная со следующей минуты, после окончания срока хранения. Если свободных ячеек не находится, то багаж не принимается в камеру хранения.
Найдите количество багажей, которое будет сдано в камеры
Входные данные.
В первой строке входного файла находится число K — количество ячеек в камере хранения, во второй строке файла
Выходные данные.
Программа должна вывести два числа: количество сданных в камеру хранения багажей и номер ячейки, в которую примут багаж у последнего пассажира, который сможет сдать багаж.
Типовой пример организации данных:
2
4
30 1000
60 100
61 1100
1010 1440
Для указанного примера багаж смогут сдать первый, второй и четвёртый пассажир. Последний пассажир сдаст свой багаж в ячейку один, так как к этому моменту первая и вторая ячейка будут свободны.
Ответ:
Считаем файл в массив и отсортируем его. Будем последовательно заполнять каждую ячейку, проверяя, чтобы время укладки нового багажа отличалось от времени забора багажа предыдущим пассажиром
Приведём решение на языке Python.
f = open('26.txt')
k = int(f.readline())
n = int(f.readline())
a = sorted([list(map(int, i.split())) for i in f])
count = 0
maxt = kposled = 0
for i in range (1, k+1):
start = 0
for x in a:
if x[0]-start >= 1 and x[0] > 0 and x[1] > 0:
count +=1
start = x[1]
if x[0] >= maxt:
maxt = x[0]
kposled = i
x[0] = -1
x[1] = -1
print(count, kposled)
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 586 3.
Ответ: 586 3.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Евгения Джобса (без сортировки, с использованием словаря).
Для наиболее удобного поиска багажа заведем словарь вида «время сдачи»: «времена выдачи». Так как в задаче не указано, что нет багажей, которые сдаются одновременно, необходимо предусмотреть хранение нескольких багажей с одинаковым временем сдачи. При таком изменении мы можем определять есть ли багажи с проверяемым временем сдачи за O(1) с помощью команды
from collections import defaultdict
with open('26.txt') as f:
k = int(f.readline())
n = int(f.readline())
bags = defaultdict(list)
for i in range(n):
a, b = map(int, f.readline().split())
bags[a].append(b)
storage = [-1]*(k+1) # хранилище
last = cnt = 0
for time in range(1440): # перебираем минуты
if time in bags: # есть багаж в очереди
for end in bags[time]:
for cell in range(1,k+1):
if storage[cell] == -1:# пустая ячейка
storage[cell], last = end, cell
cnt += 1
break
for cell in range(k):
if storage[cell] == time: # багаж забирают
storage[cell] = -1 # освобождаем ячейку
print(cnt, last)
Приведём решение Анатолия Хачатурова на языке Python.
f = open('26.txt')
k = int(f.readline())
n = int(f.readline())
data = [list(map(int, i.split())) for i in f]
data = sorted(data)
sp = []
for n in range(k):
sp.append([0])
c = 0
spi = []
for r in data:
for place in sp:
if r[0] >= place[0]:
c +=1
place.remove(place[0])
place.append(r[1] + 1)
spi.append(sp.index(place))
break
print(spi[-1] + 1, c)