Тема 26. Обработка целочисленной информации с использованием сортировки
26.07 Прочие прототипы
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела обработка целочисленной информации с использованием сортировки
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#86044

Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале и минимальное возможное суммарное время проведения всех мероприятий.

Входные данные.

В первой строке входного файла находится натуральное число N — количество заявок на проведение мероприятий (натуральное число, не превыщающее 1000).

Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятия (каждое из чисел натуральное, не превосходящее 1440).

Запишите в ответе два числа через пробел: максимальное количество мероприятий и минимальное суммарное время проведения всех мероприятий мероприятия.

Вложения к задаче
Показать ответ и решение

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

’’’
Идея решения:
В самом начале мы найдём максимальное количество мероприятий, которые мы можем совершить,
затем посчитаем суммарное количество минут проведения всех мероприятий.
Дело в том, что мы можем убрать какое-то мероприятие из расписания, взять какое-то другое и при этом получить
меньшее суммарное время.
Именно это мы и будем делать, убирать какое-то мероприятие, ставить в расписание новое,
 которое возможно провести при текущем расписании и считать кол-во минут.
’’’
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)


Ответ: 40 837

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!