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

Решение 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)