Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобожденную ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит.
Входные данные представлены в файле 26-111.txt. В первой строке входного файла находится натуральное число 
, не превышающее 1000, – количество ячеек в камере хранения. Во второй строке – натуральное число 
(
1000), обозначающее количество пассажиров. Каждая из следующих 
строк содержит два натуральных числа, каждое из которых не превышает 1440: указанное в заявке время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала суток).
Определите максимальную нечетную сумму двух промежутков времени, в течение которого багаж какого-либо пассажира находился в камере хранения.
f = open(’26-111.txt’)
k = int(f.readline()) # Количество ячеек
n = int(f.readline()) # Количество пассажиров
a = sorted([list(map(int, i.split())) for i in f]) # Время сдачи багажа
cells = [[] for i in range(k)] # Ячейки
pax = [] # Пассажиры
c = 0 # Счетчик пассажиров, сдавших багаж
for i in a: # Для каждого пассажира
for j in cells: # проверяем все ячейки
# Если ячейка пустая или успевает освободиться
if (not j) or (i[0] > j[-1][1]):
j.append(i) # Cкладываем багаж в ячейку
pax.append(i[1]-i[0]) # Время нахождения багажа в ячейке
c += 1 # Увеличиваем счетчик пассажиров
break # Останавливаем цикл, так как уже разместили багаж
mx = 0 # Обычный перебор (долго для больших файлов)
for i in range(len(pax)-1):
for j in range(i+1, len(pax)):
# Если сумма времени больше текущего максимума и нечетная
if ((pax[i]+pax[j]) > mx) and ((pax[i]+pax[j]) % 2 != 0):
mx = pax[i]+pax[j]
print(mx)
mx1 = mx2 = 0 # Четный и нечетный максимумы # Эффективный перебор
for i in pax:
if i % 2 != 0 and i > mx1: # Если время нечетное и больше нечет. макс-ма
mx1 = i
if i % 2 == 0 and i > mx2: # Если время четное и больше четного максимума
mx2 = i
print(mx1+mx2)