Багаж одного пассажира размещается в одной свободной ячейке с
Условие
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения.Задание 26В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты.Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки. Входные данные.В первой строке входного файла находится натуральное число K, не превышающее 1000, — количество ячеек в камере хранения.Во второй строке — натуральное число N (N ≤ 1000), обозначающее количество пассажиров. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанное в заявке время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала суток).Запишите в ответе два числа: количество пассажиров, которые смогут воспользоваться камерой хранения, и номер последней занятой ячейки.Типовой пример организации данных во входном файле:2530 6040 100059 6061 10001010 1440При таких исходных данных положить вещи в камеру хранения смогут первый, второй, четвёртый и пятый пассажиры.Последний пассажир положит вещи в ячейку 1, так как ячейки 1 и 2 будут свободны.Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Ответ:
Ответ
34453
Решение по шагам
Как рассуждать
Решение. Считаем файл в массив и отсортируем его. Будем последовательно заполнять каждую ячейку, проверяя, чтобы время укладки нового багажа отличалось от времени забора багажа предыдущим пассажиром на 1 и более. Также будем запоминать номер последней ячейки, куда был сдан багаж. Приведём решение на языке 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 = 0maxt = kposled = 0for 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] = -1print(count, kposled) В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 344
Осталось ещё 1 шаг — откроются после входа:
- Шаг 2
Бесплатно · займёт минуту