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

Решение (Excel/LibreOffice)
Откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice.
Воспользуемся настраиваемой сортировкой, на первый уровень расположим столбец (по возрастанию), на второй - столбец (по возрастанию). В ячейку запишем формулу =ЕСЛИ(И(A1=A2;B2-3=B1);1;0), скопируем её на все свободные клеточки этого столбца. Находим первую единицу в столбце . Выписываем в ответ минимальный номер ряда и максимальный номер свободного места.

Решение (Python)

file = open(’26__14etr.txt’)
n = int(file.readline())

arr = sorted(list(map(int,i.split())) for i in file) # сортируем данные из файла

# проход по занятым местам
for i in range(len(arr)-1):
    # если два рядом стоящих в списке места находятся в одном ряду и между ними есть два места
    if arr[i][0] == arr[i+1][0] and arr[i][1] + 3 == arr[i+1][1]:
        print(arr[i][0],arr[i][1]+2)

Решение (Excel/LibreOffice)

Откроем файл в электронной таблице, переместим в другое место первое строку и воспользуемся настраиваемой сортировкой. Отсортируем данные следующим образом: Столбец В по возрастанию и столбец А по возрастанию. Удалим пары чисел, в которых хотя бы одно число больше 9000, такие рейсы мы не сможем осуществить, так как они будут совершены не в рабочее время. После того как удалили ненужные рейсы в ячейку запишем значение , а в ячейку запишем следующую формулу:

С помощью данной формулы мы будем получать время прилета последнего совершенного рейса в намем расписании. Протянем формулу до конца таблицы. В ячейку запишем 1, а в ячейку запишем следующую формулу:

Проверяем, что если изменилось время прилета последнего совершенного рейса, то есть добавили новый рейс в наше расписании, то добавляем 1 к счётчику совершенных рейсов. Протянем формулу до конца таблицы. Выделим столбец D и посмотрим максимальное значение - оно равно 63, это и есть первый ответ. Посмотрим время прилета 62-ого рейса. Оно равно 8893. В столбце Е для всех рейсов, у которых в столбце D указано 63, запишем следующую формулу:

С помощью этой формулы определим минимальное время вылета 63-ого рейса в нашем расписании. Он равен 8911. Полный ответ: 63 8911.

Решение (Python)

with open(’26_5__1vv34.txt’) as f:
    # a - общая продолжительность рабочего дня аэропорта
    # b - количество запланированных рейсов
    a, b = map(int, f.readline().split())
    pol = [list(map(int, f.readline().split())) for _ in range(b)]

# Для оптимального составления расписания, в котором можно обеспечить макс. количество вылетов,
# сортируем список так, чтобы время прилета шло по возрастанию для раннего прилёта самолётов
pol.sort(key=lambda x: (x[1], x[0]))
count = [pol[0]]
for fl in pol:
    # Если при сопоставлении времени вылета текущего самолёта и прилёта предыдущего всё устраивает,
    # то добавляем самолёт в список
    if fl[0] >= count[-1][1] and a >= fl[1]:
        count.append(fl)

# Найдём последний самолёт с минимальным временем взлёта
mn = 10_000
for fl in pol:
    if fl[0] >= count[-2][1] and a >= fl[1]:
        mn = min(mn, fl[0])

# Выводим кол-во удавшихся рейсов и время вылета последнего рейса
print(len(count), mn)

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

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

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

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

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

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

Максимальное число в столбце D и будет количеством мероприятий - 40. А максимальное из чисел в столбце А напротив максимального числа из столбца D будет временем начала последнего мероприятия - 1299. Из него нужно вычесть время окончания предпоследнего мероприятия, записанное в столбце C напротив предмаксимального числа в столбце D - 39. Получим второй ответ: 1299 - 1273 = 26.

 

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

Нам нужно набрать максимальное количество мероприятий. Для этого отсортируем сначала по времени конца, потом по времени начала. Возьмём первое мероприятие, а дальше пойдём по остальным заявкам. Будем держать в голове время окончания последнего взятого меропрития, время окончания предпоследнего мероприятия, а также времена начал мероприятий, которые можно взять в качестве последних для того, чтобы затем найти максимальный перерыв между двумя последними мероприятими.

Для каждой заявки после первой мы смотрим, если её можно провести после предыдущего мероприятия, то мы его берём, ставим последним, обновляем предпоследнее мероприятие, а список возможных начал последних мероприятий заполняем только взятым мероприятием. Если же мероприятие нельзя провести, то добавляем его в список возможных начал, ведь его можно попробовать взять вместо последнего взятого в конце.

После того, как мы прошлись по всем заявкам, мы имеем максимальное количество мероприятий, а также список мероприятий, которые можно взять как последнее вместо того, что мы уже взяли. Ведь у них время начала может быть позже, что увеличит перерыв между двумя последними. Этот перерыв будет равен максимальному времени начала из возможных минус время конца предпоследнего мероприятия.

# Открываем файл и считываем количество заявок
file = open("1_26_conf.txt")
n = int(file.readline())

# Считываем заявки
confs = [list(map(int, i.split())) for i in file]

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

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

for start, end in confs:
    # Может начаться новое - начинаем, не может - добавляем в список возможных
    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)

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

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

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

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

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

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

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

Последние два мероприятия необходимо просчитать отдельно, для этого в ячейку E845 - напротив первого возможного предпоследнего мероприятия, запишем следующую формулу:

С её помощью мы определили, может ли это мероприятие быть предпоследним, и если да - сохранили время его окончания. В ячейку F845 запишем следуюзщую формулу:

Таким образом мы нашли мероприятие, которое может начаться после предпоследнего с минимальным возможным временем начала. Найдём разность между началом последнего и концом предпоследнего, записав в ячейку G845 следующую формулу:

Растянем эти три формулы до конца таблицы, и в ответ запишем минимальное значение из столбца G.

 

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

f = open(’2_26_conf.txt’)
n = int(f.readline())

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

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

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

for conf in confs:
    start, end = conf
    # Может начаться новое - начинаем
    if start >= last_end:
        cnt += 1
        last_end = end
        program.append(conf)

# Время окончания пред-предпоследнего мероприятия
new_end = program[-3][1]
mn = 10 ** 10
# Цикл начиная со следующего после пред-предпоследнего
for conf in range(confs.index(program[-3]) + 1, len(confs)):
    start, end = confs[conf]
    # Если текущее может стать предпоследним
    if start >= new_end:
        # Все возможные варианты последнего для текущего предпоследнего
        variants = [i[0] for i in confs[conf + 1:] if i[0] >= end]
        # Если есть хоть один вариант - обновляем минимальную разность между
        # началом последнего и концом предпоследнего
        if variants:
            mn = min(mn, abs(min(variants) - end))

print(cnt, mn)

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

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

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

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

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

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

Максимальное число в столбце D и будет количеством мероприятий — 38.

Минимальное допустимое время начала последнего мероприятия найдём с помощью следующей формулы, в качестве диапазона выбрав отрезок столбца А напротив максимального числа в столбце C:

 

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

Чтобы набрать максимальное количество мероприятий, нужно отсортировать в первую очередь по времени окончания, ведь чем раньше закончится какое-либо мероприятие, тем раньше можно начать следующее. Возьмём первое мероприятие в получившемся списке, а затем пойдём по остальным, запоминая, когда заканчивается последнее взятое. Если новое мероприятие можно провести после последнего, то берём его. Так мы найдём максимальное количество мероприятий.

Чтобы найти, какое мероприятие можно поставить последним, чтобы у него было минимальное время начала, нам нужно как-то заменить последнее мероприятие. То есть нам нужно знать, когда заканчивается предпоследнее мероприятие, чтобы посмотреть, что можно после него поставить. Также нам нужен список мероприятий, которые не вошли в расписание, ведь их потенциально можно вставить вместо последнего. В конце просто найдём из этого списка самое раннее, что можно поставить после предпоследнего.

# Открываем файл
file = open("3_26_conf.txt")
n = int(file.readline())

# Считываем заявки
confs = [list(map(int, i.split())) for i in file]

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

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

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

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

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

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

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

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

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

Прежде чем определять ответ необходимо удалить из таблицы все строки, в которых в столбце B значение больше времени окончания работы аэропорта — это строки начиная с номера 4502, так как в ней в столбце B значение 8073, что больше чем 8071 из условия.

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

Максимальное возможное время вылета последнего самолёта найдём как наибольшее число из всех возможных времён вылета последнего — максимальное число из отрезка столбца A напротив максимального числа из столбца D — 135. Таким образом ответ — 7978.

 

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

После считывания файла нужно убрать все рейсы, которые прилетят после закрытия аэропорта. Чтобы максимизировать количество рейсов, их следует отсортировать по времени прилёта, ведь чем раньше самолёт улетит, тем раньше можно пустить следующий. Возьмём первый рейс, а далее будем смотреть, может ли полететь следующий рейс, сравнив его с предыдущим. Для этого будем следить за тем, когда прилетает последний взятый рейс.

Чтобы найти время самого позднего последнего рейса, создадим список начал возможных вылетов. Когда мы будем брать рейс, список будем сбрасывать до только что взятого вылета. Если же рейс не берём, то добавляем его в этот список. Таким образом мы будем иметь либо список всех рейсов, которые можно взять вместо того, что мы взяли последним, чтобы найти самое позднее последнее.

# Открываем файл и считываем продолжительность работы и количество рейсов
file = open("4_26_conf.txt")
dur, n = map(int, file.readline().split())

# Считываем рейсы
planes = [list(map(int, i.split())) for i in file]

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


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

planes = planes[:ind]

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

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

print(cnt, max(last_starts))

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

Сначала переносим данные в 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)

Решение 1 (Повторный перебор)

Нам нужно набрать максимальное количество мероприятий с минимальным суммарным временем. Для максимального количества отсортируем в первую очередь по времени окончания, а для первого приближения к минимальному суммарному времени также отсортируем во вторую очередь по длительности мероприятия.

Создадим список, куда мы будем помещать взятые мероприятия, ведь мы потом будем пробовать поменять некоторые, чтобы сэкономить время. Теперь пройдёмся по мероприятиям и будем брать те, что начинаются не раньше, чем заканчивается последнее, а также для удобства будем ещё дописывать туда длительность мероприятия.

Теперь нужно попробовать заменить взятые на более короткие. Для этого отсортируем все заявки в первую очередь по длительности, а во вторую — по времени начала. Мы хотим брать самые короткие мероприятия и пробовать их заменять. Пройдёмся по только что отсортированному списку. В этом цикле пойдём по взятым мероприятиям без последнего и будем проверять, что мероприятие, на которое мы хотим заменить, короче и вписывается в расписание. Если замена успешна, пробуем заменить на следующее мероприятие, завершая внутренний цикл. В итоге суммарное время найдётся как сумма длин взятых мероприятий.

# Открываем файл и считываем количество мероприятий
f = open("6_26_conf.txt")
n = int(f.readline())

# Считываем заявки
requests = [list(map(int, i.split())) for i in f]

# Сортируем список заявок для их наибольшего количества и минимальной
# суммарной длительности
requests.sort(key=lambda x: (x[1], x[1] - x[0]))

# Список взятых мероприятий
hall = []

# Проход по всем мероприятиям
for start, end in requests:
    # Добавляем конференцию в список, если её начало позже или
    # равно окончанию предыдущей конференции
    if not hall or start >= hall[-1][1]:
        hall.append([start, end, end - start])

# Отсортируем заявки по длительности
times = sorted([x for x in requests], key=lambda x: (x[1] - x[0], x[0]))

# Пройдёмся по мероприятиям, на которые хотим заменить
for i in times:
    for j in range(0, len(hall) - 1):
        # Проверяем, что мероприятие короче и вписывается в расписание
        if (
            (i[1] - i[0]) < (hall[j][2])
            and (hall[j + 1][0] >= i[1])
            and (i[0] >= hall[j][0])
        ):
            # Заменяем конференцию
            hall[j] = [i[0], i[1], i[1] - i[0]]
            # Переходим к замене на следующее мероприятие
            break
# Выводим ответ
print(len(hall))
print(sum([i[2] for i in hall]))

 

Решение 2 (Динамика)

Идея динамического решения заключается в том, что если мы уже знаем какой-то набор мероприятий, а именно нам нужно время окончания последнего мероприятия, количество мероприятий и суммарная их длина, то довольно легко добавить новое.

Наборы мы будем отслеживать в двух списках: times и counts. i-е элементы этих списков отвечают за суммарное время и количество мероприятий в наборах, где i-й элемент является последним.

Мы берём новое мероприятие и какой-то набор, к которому мы хотим его прибавить. Если новое вставляется в набор (то есть оно вписывается после последнего), то возможны два сценария, при которых нужно обновлять набор нового:

1. Количество мероприятий из набора с новым мероприятием больше, чем в наборе нового мероприятия. Тогда мы обновляем набор нового мероприятия новым количеством и временем, объединяем с набором, к которому прибавляем.
   
2. Количество то же, но время стало меньше. Снова обновляем время набора
   

Также не забудем отсортировать массив, можно как по времени начала, так и по времени окончания, ведь нам нужно, чтобы все уже известные наборы были не позже нового мероприятия. Поэтому какая-то сортировка обязательно нужна. Иначе возможно такое, что мы найдём набор для мероприятия, которое начинается, например в 500, а потом попытаемся прибавить к нему мероприятие, которое начинается в 30. А по логике решения вот это мероприятие должно было рассматриваться в набор для 500 намного раньше.

Теперь для каждого мероприятия мы знаем, какое максимальное количество мероприятий с минимальным суммарным временем можно провести, рассматривая только все мероприятия до него. Ответ же найдётся так: надо найти набор с максимальным количеством и временем. Для этого сначала ищем максимальное количество. А затем минимальное время, соответствующее набору с максимальным количеством.

# Открываем файл
file = open("6_26_conf.txt")
# Записываем число n
n = int(file.readline())
# Cчитываем и записываем в список все конференции
meets = [list(map(int, i.split())) for i in file]

# Сортируем по времени для правильного порядка
meets.sort()
# Cоздаём список со временем проведения каждого мероприятия
times = [end - start for start, end in meets]
counts = [1] * n  # Создаём список с количеством проведённых мероприятий

# Перебираем заявки
for new_index in range(n):
    # Начало и конец нового мероприятия
    start_new, end_new = meets[new_index]
    # Перебираем все мероприятия с известными наборами
    for old_index in range(new_index):
        # Начало и конец известного мероприятия
        start_old, end_old = meets[old_index]
        # Проверяем, добавляется ли новое мероприятие в набор
        if end_old <= start_new:
            # Теперь смотрим, выгодно ли это по критерию количества или времени
            if counts[old_index] + 1 > counts[new_index]:
                # Обновляем количество и время
                counts[new_index] = counts[old_index] + 1
                times[new_index] = end_new - start_new + times[old_index]
            elif (
                counts[old_index] + 1 == counts[new_index]
                and end_new - start_new + times[old_index] < times[new_index]
            ):
                # Обновляем время
                times[new_index] = end_new - start_new + times[old_index]

# Находим максимальное количество проведённых мероприятий
max_count = max(counts)
# Находим минимальное время, при котором кол-во мероприятий максимально
min_time = min(times[i] for i in range(n) if counts[i] == max_count)

# Выводим ответ
print(max_count, min_time)
                                                                                                  
                                                                                                  

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

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

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

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

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

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

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

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

В столбце E мы посчитаем длительность прошедших рейсов. В ячейку E1 запишем разницу между B1 и A1, а в ячейку E2 запишем следующую формулу и растянем её до конца таблицы:

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

Общая длительность рейсов - 5130.

 

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

f = open(’7_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]

# Время окончания последнего рейса
last_end = plains[0][1]
cnt = 1
sm = plains[0][1] - plains[0][0]

for start, end in plains:
    # Может начаться новое - начинаем, не может - добавляем в список возможных
    if start >= last_end:
        cnt += 1
        last_end = end
        # Увеличиваем время общей длительности
        sm += end - start

print(cnt, sm)

Решение (Excel/LibreOffice)

Переносим данные в Excel, удаляем первую строку файла. Переходим в раздел «Настраиваемая сортировка» и сортируем сначала по столбцу B по возрастанию, а затем – по столбцу А по возрастанию.

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

и растянем её до конца таблицы.

В ячейку D1 запишем 1, а в ячейку D2 запишем следующую формулу:

растянем её до конца таблицы.

Максимальное число в столбце D будет ответом на первый вопрос: количество мероприятий – 97.

Чтобы ответить на второй вопрос найдем строку, где проходит 49 мероприятие (то есть то, что в середине). Время начала 49-го мероприятия: 1040, время его окончания – 1055. Значит, его продолжительность 15.

Решение (Python)

f = open(’26_10__4107m.txt’)
n = int(f.readline())

# считываем данные из файла
confs = [list(map(int, i.split())) for i in f]

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

for conf in confs: # проход по всем мероприятиям
    if conf[0] >= schedule[-1][1]: # если начало текущего мероприятия больше или равно окончанию последнего мероприятия, которое мы взяли в расписание
        schedule.append(conf) # тогда добавляем текущее мероприятие в список
print(len(schedule)) # вывод количества проведенных мероприятий
# мероприятия, которые могут быть 49-ыми по счёту
ost_confs = [i[1]-i[0] for i in confs if i[0] >= schedule[47][1] and i[1] <= schedule[49][0]]
# вывод максимальной длительности 49-ого мероприятия
print(max(ost_confs))

f = open(’26.txt’) # Открываем файл
n = int(f.readline()) # Kоличество заявок
# Записываем времена начала, окончания занятий и кол-во учеников
a = [list(map(int, i.split())) for i in f]
a.sort(key=lambda x:x[1]) # Сортировка по времени окончания занятий
price = [i[2] for i in a] # Cписок кол-ва учеников
tm = [i[1]-i[0]+1 for i in a] # Список длительностей занятий
cnt = [1]*n # Список количества занятий

for i in range(1, n): # Перебираем заявки
    for j in range(i): # Все предыдущие заявки до текущей
    # Если занятий j заканчивается до начала занятий i
        if a[j][1] < a[i][0]:
        # Если сумма кол-ва учеников i-й и j-й заявок больше текущей максимальной
            if price[j]+a[i][2] > price[i]:
                # Обновляем максимальное кол-во учеников для i-й заявки
                price[i] = price[j]+a[i][2]
                # Обновляем общую длительность занятий
                tm[i] = tm[j]+a[i][1]-a[i][0] + 1
                # Обновляем количество занятий
                cnt[i] = cnt[j]+1
            elif price[j]+a[i][2] == price[i]:
              if tm[i] > tm[j]+a[i][1]-a[i][0] + 1:
                tm[i] = tm[j]+a[i][1]-a[i][0] + 1
mx = max(price) # Mаксимальное количество учеников за день
for i in range(n):
    if price[i] == mx:
        print(tm[i]) # Длительность всех выбранных занятий
        print(mx)