Программа курса Урок 140 из 148 · Десять дверей и полевой набор
Десять дверей и полевой набор

Итоговый экзамен 2: окно для каждого сервера

ИИ выключен Это итоговый экзамен, подобранный к базовому экзамену, который вы сдавали в первом модуле: тот же навык на другой задаче той же сложности, поэтому прочитайте её правила заново (код базового экзамена не перенесётся). Наставник отключён, подсказок нет. Работайте одни. Курс ставит его рядом с вашим базовым экзаменом в следующем уроке.

Команде эксплуатации нужно окно, когда каждый сервер кластера простаивает, чтобы обновить их вместе. Архив каждого сервера записывает окна, когда он простаивал, и архив берёт плату за каждую полученную запись. Архивы уходят на годы назад.

Небольшой пример

from creative.budget import Tape
idle = [[(0, 10), (30, 60), (90, 10**9)],     # server A
        [(0, 40), (50, 10**9)],               # server B
        [(20, 10**9)]]                        # server C
maintenance_window([Tape(s) for s in idle], 0, 10)   # -> 30  (A and B idle from 30 to 40, C from 20)
maintenance_window([Tape(s) for s in idle], 0, 15)   # -> 90  (B is busy from 40 to 50, A from 60 to 90)
maintenance_window([Tape(s) for s in idle], 55, 5)   # -> 55  (55 + 5 = 60: touching the end is fine)
Твоя очередь

Напишите maintenance_window(servers, after, length). servers - список Tape, по одному на сервер. Каждый содержит окна простоя этого сервера как пары минут (start, end), отсортированные по start, никогда не перекрывающиеся и не соприкасающиеся (между двумя окнами сервер занят). Окно - простой от start до end, не включая его, и последнее окно каждого сервера заканчивается в 10**9, поэтому ответ всегда есть. Верните самую раннюю минуту t >= after, такую что каждый сервер простаивает весь промежуток [t, t + length).
Бюджет: 50 серверов примерно по 2 000 окон (около 100 000 записей), а after обычно приходится на месяцы вглубь данных. Один поиск может прочитать всего не больше 10 000 записей. len() у Tape бесплатен. Tape ведёт себя как список только для чтения (индексация, срезы и циклы работают), и каждая выданная запись считается одним чтением.

ИИ выключен: нет тьютора, подсказок или готового решения для этой задачи. Только ваши собственные мысли.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.