Задание 26 ЕГЭ: окна приёма посетителей

Окна приёма посетителей: кто попадёт на приём. Тема номера — обработка данных и моделирование. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

В многофункциональном центре посетителей принимают специалисты в окнах, пронумерованных натуральными числами начиная с 1. Для каждого посетителя известны время начала и время окончания приёма (в минутах от начала суток). Посетители обращаются в порядке возрастания времени начала приёма, при равном начале — в порядке возрастания времени окончания.

Посетителя принимает свободный специалист в окне с наименьшим номером. Специалист, закончивший приём в минуту t, может принять следующего посетителя начиная с минуты t + 1. Если в момент обращения свободных окон нет, посетитель уходит.

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

Входные данные. В первой строке файла 26.txt записаны два натуральных числа: K — количество окон и N — количество посетителей. В каждой из следующих N строк — два целых неотрицательных числа: время начала и время окончания приёма.

Запишите два числа через пробел.

Скачать файл к примеру

Решение

Сортируем заявки по началу (при равенстве — по окончанию) и моделируем: для каждого окна помним, когда закончится текущий приём. Посетитель получает первое окно, освободившееся строго раньше минуты его обращения. Среди посетителей с одинаковым началом окно с меньшим номером достаётся первому из них, поэтому номер запоминаем только при увеличении времени начала.

Ответ: 2203 7.

f = open('26.txt')
k, n = map(int, f.readline().split())
reqs = sorted(tuple(map(int, f.readline().split())) for _ in range(n))
end = [-1] * (k + 1)                 # end[w] — минута окончания последнего приёма в окне w
served, last = 0, (-1, 0)
for st, en in reqs:
    for w in range(1, k + 1):
        if end[w] < st:              # окно свободно с минуты end[w] + 1
            end[w] = en
            served += 1
            if st > last[0]:
                last = (st, w)       # при равном начале первым получит окно меньший номер
            break
print(served, last[1])

Решить такую задачу — новый вариант с проверкой