Мобильная версияВ кампусе 𝑘 классов и 𝑛 предлагаемые мероприятия, для которых
нужно определить место проведения. Каждое предлагаемое действие имеет определенное
время начала 𝑠𝑖 и время окончания 𝑓𝑖. Любое такое мероприятие должно проводиться
в одном из классов. Любой из 𝑘 классов достаточно велик, чтобы
провести любое из предложенных мероприятий, и каждый класс может проводить
не более одного занятия в любое время. Никакие два предлагаемых мероприятия не могут проводиться
в одном классе одновременно. Даже если два предложенных
действия на мгновение перекрываются (время окончания одного действия равно
времени начала другого действия), их нельзя отнести к
одному и тому же классу.
Предложенных мероприятий так много, что может не хватить
классов для проведения всех мероприятий. Желательно проводить как можно больше мероприятий. Максимум, сколько предложенных мероприятий можно
назначить для классов?
Входные данные Первая строка содержит два положительных целых числа 𝑛 и 𝑘
(1≤𝑘≤𝑛≤ 200000), представляющее количество предлагаемых мероприятий и
количество классных комнат соответственно.
В следующих 𝑛 строках содержится по два положительных целых числа: 𝑖-я
строка среди этих 𝑛 строк содержит 𝑠𝑖 и 𝑓𝑖 (1≤𝑠𝑖≤𝑓𝑖≤109),
обозначающие время начала и время окончания предлагаемого действия
Я придумал жадное решение: я сортирую классы по времени окончания, а затем проверяю можно ли присвоить класс активности на основе жадных условий
Код: Выделить всё
'''
https://open.kattis.com/problems/classrooms
'''
from collections import deque
n, k = map(int, input().split())
classes = []
for _ in range(n):
(start, end) = map(int, input().split())
classes.append((start, end))
classes.sort(key=lambda x: x[1])
queue = deque()
count = 0
for (start, end) in classes:
if queue and queue[0] < start:
queue.popleft()
queue.append(end)
count += 1
elif len(queue) < k:
count += 1
queue.append(end)
print(count)
Каков правильный подход к решению этой проблемы?
Подробнее здесь: https://stackoverflow.com/questions/592 ... -algorithm
