26.08 Составление расписания (конференц залы, аэропорты)

Решение при помощи электронных таблиц:

Сначала переносим данные в Excel, удалим первую строчку, а потом при помощи настраиваемой сортировки отсортируем в первую очередь по столбцу B, а потом по столбцу А - всё по возрастанию. Нужно сортировать по времени окончания рейса, так как чем раньше один кончится, тем раньше сможет начаться следующий.

В ячейку C1 запишем значение ячейки B1, в ячейку C2 запишем следующую формулу и растянем её до конца таблицы:

Таким образом у нас в столбце C будет храниться время окончания последнего (на данный момент) рейса. Каждый новый вылет мы проверяем - может ли он начаться после предыдущего последнего, и если да - сохраняем уже новое время окончания, иначе дублируем старое.

В столбце D мы посчитаем количество прошедших рейсов. В ячейку D1 запишем 1, а в ячейку D2 запишем следующую формулу и растянем её до конца таблицы:

Если сменилось время окончания - увеличиваем счётчик, иначе дублируем предыдущий.

Прежде чем определять ответ необходимо удалить из таблицы все строчки, в которых в столбце B значение больше времени окончания работы аэропорта - это строчки начиная с номера 6248, так как в ней в столбце B значение 8726, что больше чем 8725 из условия.

Максимальное число в столбце D и будет количеством рейсов - 154.

Максимальное возможное время вылета последнего самолёта найдём как наибольшее число из всех возможных времен вылета последнего - максимальное число из отрезка столбца A напротив максимального числа из столбца D - 154. Чтобы получить второй ответ, из времени начала последнего рейса вычтем время окончания предпоследнего: 8648 - 8628 = 20.

Решение при помощи программы:

f = open(’5_26_conf.txt’)
dur, n = map(int, f.readline().split())

plains = [list(map(int, i.split())) for i in f]

# Сортируем по времени окончания, так как
# чем раньше один кончится, тем раньше сможет начаться следующий
plains.sort(key=lambda x: (x[1], x[0]))


# Уберем все рейсы, кончающиеся после закрытия аэропорта
ind = len(plains)
for i in range(len(plains)):
    if plains[i][1] > dur:
        ind = i
        break

plains = plains[:ind]

# Время окончания предпоследнего рейса
prev_end = 0
# Время окончания последнего рейса
last_end = plains[0][1]
# Все возможные времена начала последнего рейса
last_starts = [plains[0][0]]
cnt = 1

for start, end in plains:
    # Может начаться новое - начинаем, не может - добавляем в список возможных
    if start >= last_end:
        cnt += 1
        # Смещаем последнее в предпоследнее
        prev_end = last_end
        last_end = end
        # Обнуляем список с началами
        last_starts = [start]
    else:
        last_starts.append(start)

print(cnt, max(last_starts) - prev_end)