Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения.
В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты.
Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.
Входные данные.
В первой строке входного файла находится натуральное число K, не превышающее 1000, — количество ячеек в камере хранения.
Во второй строке — натуральное число N (N ≤ 1000), обозначающее количество пассажиров. Каждая из следующих
Запишите в ответе два числа: количество пассажиров, которые смогут воспользоваться камерой хранения, и номер последней занятой ячейки.
Типовой пример организации данных во входном файле:
2
5
30 60
40 1000
59 60
61 1000
1010 1440
При таких исходных данных положить вещи в камеру хранения смогут первый, второй, четвёртый и пятый пассажиры.
Последний пассажир положит вещи
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Ответ:
Считаем файл в массив и отсортируем его. Будем последовательно заполнять каждую ячейку, проверяя, чтобы время укладки нового багажа отличалось от времени забора багажа предыдущим пассажиром
Приведём решение на языке Python.
f = open('1_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)
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 344 53.
Ответ: 344 53.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Анатолия Чернышева на языке Python.
def solve(K, passengers):
lockers = [-1]*K
served_passengers = 0
last_locker = -1
for arrival, departure in sorted(passengers):
for i in range(K):
if lockers[i] < arrival:
lockers[i] = departure
served_passengers += 1
last_locker = i + 1
break
return served_passengers, last_locker
f = open('1_26.txt')
K = int(f.readline())
N = int(f.readline())
passengers = []
for _ in range(N):
arrival, departure = map(int, f.readline().split())
passengers.append((arrival, departure))
print(*solve(K, passengers))