Известно, что путь автобуса проходит через А городов. У контроллёра есть список, содержащий В заявок на поездку. В каждой заявке указано на какой остановке пассажир будет садиться в автобус и на какой остановке он выйдет. Известно, что в автобусе всего С мест. На остановках сначала происходит высадка пассажиров, затем посадка. Когда пассажиры приходят на посадку, контролёр в первую очередь пропускает того, чей путь дольше остальных. При этом место пассажира определеяется как свободное и чей номер минимален.
Определите количество пассажиров, которые смогут добраться до пункта своего назначения и в скольких участках между соседними городами будут полностью заняты места.
Входные данные. В первой строке файла задано три числа: M (2 
M 
3000) – количество населенных пунктов, в которых останавливается автобус, K (1 
K 
1000) – количество мест в автобусе и N (1 
N 
10000) – количество пассажиров, желающих проехать на автобусе. В каждой из последующих N строк располагаются пары чисел: сначала номер населенного пункта, откуда хочет начать свою поездку пассажир, затем номер населенного пункта, где пассажир собирается сойти с автобуса.
Выходные данные. Два числа через пробел: сначала количество участков между соседними городами, в которых места будут полностью заняты, затем количество пассажиров, которые смогут добраться до нужной им остановки.
Решение (Python)
f = open(’26_15__1vv3h.txt’)
# Считали первую строку
a, c, b = map(int, f.readline().split())
# Считали данные о пассажирах
data = []
for i in range(b):
x, y = map(int, f.readline().split())
data.append([x, y])
data.sort(key=lambda x: (x[0], -x[1])) # Отсортировали по возрастанию первого элемента и убыванию второго
# Создали список для каждого из мест. places[i][point] отвечает за i-ое место и будет хранить 0 или 1, в зависимости
# от того, занято ли оно в населенном пункте point.
places = [[0] * (a + 1) for i in range(c)]
counter = 0 # Количество пассажиров, которые смогут добраться до нужной им станции
cnt_areas = 0 # Количество участков между соседними городами, в которых места будут полностью заняты
# Перебираем для каждого пассажира места и ищем свободные
for st, fin in data:
for i in range(c):
# Если место свободно на данном населённом пункте, то сажаем сюда пассажира
if places[i][st] == 0:
counter += 1
# Резервируем данное место на все населённые пункты с st по fin не включительно. То есть место будет свободно
# в населённом пункте с индексом fin, так как пассажир на нём сойдёт.
for j in range(st, fin):
places[i][j] = 1
break
# Перебираем для каждого населённого пункта все места и смотрим, чтобы все эти места были заполнены
for p in range(1, a + 1):
if all(places[i][p] == 1 for i in range(c)):
cnt_areas += 1
print(cnt_areas, counter)