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

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

Задача 1#86041

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

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

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

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

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

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

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

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

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

=ЕСЛИ(A2>=C1;B2;C1)

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

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

=ЕСЛИ(C2<>C1;D1+1;D1)

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

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

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

=МИНЕСЛИ(A903:A966;A903:A966;»="&C902)

 

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

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]))

Ответ: 38 1288

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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