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.

 

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

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

# Время окончания предпоследнего мероприятия
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:

 

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

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

# Время окончания предпоследнего мероприятия
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, удалим первую строчку, а потом при поvощи настраиваемой сортировки отсортируем в первую очередь по столбцу B, а потом по столбцу А - всё по возрастанию. Нужно сортировать по времени окончания рейса, так как чем раньше один кончится, тем раньше сможет начаться следующий.

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

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

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

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

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

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

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

 

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

f = open(’4_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]
# Все возможные времена начала последнего рейса
last_starts = [plains[0][0]]
cnt = 1

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

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

’’’
Идея решения:
В самом начале мы найдём максимальное количество мероприятий, которые мы можем совершить,
затем посчитаем суммарное количество минут проведения всех мероприятий.
Дело в том, что мы можем убрать какое-то мероприятие из расписания, взять какое-то другое и при этом получить
меньшее суммарное время.
Именно это мы и будем делать, убирать какое-то мероприятие, ставить в расписание новое,
 которое возможно провести при текущем расписании и считать кол-во минут.
’’’
file = open(’6_26_conf.txt’)
count_race = int(file.readline())
array_race = []
for i in file:
    temp = i.split()
    start,end = int(temp[0]),int(temp[1])
    # добавляем в список мероприятий время старта, конца, а также кол-во минут сколько событие будет идти
    array_race.append([start,end,end-start])
# отсортируем массив, в первую очередь, по возрастанию времени окончания,
# во вторую очередь, по времени длительности,
# нас интересуют именно самые короткие по длительности мероприятия для выстраивания самого
#  оптимального расписания, c точки зрения, количества мероприятий в расписании.
array_race.sort(key = lambda x:(x[1],x[2]))
#список мероприятий, который мы проведём, закладываем изначально первый элемент из array_races
races = [array_race[0]]
#поминутный график конференц-зала. 0 обозначена минута, которая является свободной,
# никакое мероприятие в эту минуту не проходит.
#1 - в данную минуту проводится какое-то мероприятие.
schedule = [0]*2000
#поскольку первое мероприятие мы изначально положили в races,
# то в schedule также нужно заполнить 1-ами время выполнения данного процесса, от старта до его окончания
schedule[races[0][0]:races[0][1]] = [1 for j in range(races[0][0],races[0][1])]
for race in array_race:#проход по всевозможным мероприятиям
#если время текущего мероприятия больше или равно тому, что поставили в расписание последним,
    if race[0] >= races[-1][1]:
        # то текущее мероприятие может быть добавлено в список мероприятий
        races.append(race)
        # проходимся по отрезку минут проведения мероприятия
        for time in range(race[0],race[1]):
            schedule[time] = 1# помечаем, что данные минуты заняты
’’’
В строках выше мы определили максимальное количество мероприятий. Теперь будем определять минимальное время проведения всех мероприятий.
’’’
                                                                                                  
                                                                                                  
ost_race = sorted([x for x in array_race if x not in races],key = lambda x:(x[2]))#список мероприятий,
# которое мы не взяли в расписание изначально
mn = 10**10
for i in range(len(races)):#проход по всевозможным мероприятиям нашего изначального расписания
    ’’’
    В следующих 4-x строках мы делаем следующие операции:
    1. Создаём temp_races и temp_schedule, которые являются клонами изначального списка
    мероприятий и расписания
    2. Удаляем из них i-ый элемент. Для начала в расписании помечаем 0 время выполнения процесса,
    что мы собираемся удалить,  затем функцией pop удаляем его из списка мероприятий
    ’’’
    temp_races = races[:]
    temp_schedule = schedule[:]
    temp_schedule[temp_races[i][0]:temp_races[i][1]] = [0 for j in range(temp_races[i][0], temp_races[i][1])]
    temp_races.pop(i)
    for race in ost_race:#проходимся по рейсам, которые мы не взяли изначально
        if sum(temp_schedule[race[0]:race[1]]) == 0:#если в расписании ни одна минута не занята с момента
         #начала и по окончанию мероприятия
            temp_races.append(race)#то данное мероприятие можно добавить в новый список мероприятий
            for time in range(race[0], race[1]):
                temp_schedule[time] = 1 #помечаем 1-ами минуты в новом расписании
    #если длина текущего списка >= 40, то есть мы удалили элемент и нашли вместо него другое, как минимум одно
    if len(temp_races) >= 40:
        mn = min(mn,sum(temp_schedule)) #то считаем минимальное время выполнения всех мероприятий
print(len(races),mn)

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

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