ALGO·III Алгоритмы Глава 23 из 65
Жадность и электричество
Моравия, двадцатые годы: в деревни ведут электричество, и каждый километр провода стоит денег. Вы — инженер энергосети. Сначала прокладываете линии руками, потом доказываете, что рецепт «самый короткий провод первым» не ошибается. По дороге — касса, которая ошибается, бригада с расписанием и код, придуманный студентом вместо экзамена.
Алгоритмы
Опирается на: 22 · Запомнить, чтобы не считать 19 · Шесть рукопожатий 18 · Кто следующий
Что вы унесёте из главы
- отличать задачи, где жадный шаг ведёт к лучшему ответу, и доказывать это аргументом обмена
- строить минимальное остовное дерево алгоритмами Краскала и Прима и писать систему непересекающихся множеств
- сжимать текст кодом Хаффмана на куче
Прошлая глава кончилась у кассы. Динамическое программирование находит самый короткий набор монет для любой суммы, но живой кассир таблиц не заполняет. Он берёт самую крупную монету, которая влезает в сдачу, потом снова самую крупную — и с монетами тенге почему-то всегда отдаёт сдачу наименьшим числом монет. Ему везёт, или так и должно быть? Шаг, который выглядит лучшим прямо сейчас, без оглядки на то, что будет дальше, называют жадным. Иногда жадность ведёт прямо к лучшему ответу, иногда заводит в тупик. Отличать одно от другого будем на работе инженера: в моравские деревни тянут электричество, и каждый километр провода стоит денег.
Брно, 1926. Наряд первый: провода
Вот ваш первый наряд. На карте — тринадцать сёл и городков вокруг Славкова; по-немецки он Аустерлиц, тот, под которым Наполеон разбил русскую и австрийскую армии. Провод можно тянуть между любыми двумя напрямую, километр стоит везде одинаково. Ток по проводам идёт куда угодно, поэтому не нужно соединять каждое село с каждым: достаточно, чтобы от любого села до любого другого вела дорожка по проводам, пусть и через соседей. Соедините всех, потратив как можно меньше провода. Нажмите на одно село, потом на другое — между ними ляжет провод; нажмите на провод — он исчезнет.
Как вы действовали? Почти наверняка начали с коротких проводов между соседями, а длинные тянули, только когда без них было не обойтись. И вряд ли протянули провод между сёлами, которые уже связаны: такой провод замыкает круг, и ток по нему ничего нового не получит. Именно этот рецепт в 1956 году опубликует американец Джозеф Краскал: перебирать возможные провода от короткого к длинному и брать каждый, если он не замыкает круг. Если ваша сеть вышла длиннее, чем у Краскала, найдите место, где вы отступили от рецепта.
Краскал на каждом шаге берёт самый дешёвый из разрешённых проводов и никогда не передумывает. Так устроен жадный алгоритм: ответ растёт шаг за шагом, на каждом шаге берётся лучшее по простому местному правилу, и сделанный выбор уже не пересматривается. Такие алгоритмы коротки и быстры. Беда в том, что «лучшее сейчас» не обязано вести к лучшему в итоге, и пара удачных примеров тут ничего не гарантирует — нужно доказательство. Почему так строго, видно у кассы.
Касса: где жадность ошибается
Монеты тенге — 1, 2, 5, 10, 20, 50, 100 и 200 тенге. Сдачу в 18 тенге жадный кассир даёт так: десятка, пятёрка, двушка и монета в один тенге, четыре монеты. Меньше нельзя, проверьте сами. Теперь представьте страну с монетами в 1, 3 и 4 единицы. Сдача 6: жадный кассир берёт самую крупную, четвёрку, остаток 2 добирает двумя единицами — три монеты. Но две тройки дают те же 6 двумя монетами. Четвёрка казалась лучшим ходом, а оказалась ошибкой, которую потом не исправить.
Сравним жадного кассира с динамикой из главы 22, которая для каждой суммы от 1 до нужной помнит наименьшее число монет. Для каких наборов монет жадность хоть раз ошибается? Перебирать все суммы до бесконечности не придётся. В 1994 году Декстер Козен и Шмуэль Закс доказали: если жадный кассир вообще где-нибудь ошибается, то самая маленькая ошибка случается на сумме меньше, чем две самые крупные монеты вместе. Поэтому проверка конечна.
В СССР с 1961 года ходили монеты в 1, 2, 3, 5, 10, 15, 20 и 50 копеек. Всегда ли жадный кассир давал сдачу наименьшим числом монет?
Всегда — проверка ниже перебирает все суммы до 69 копеек, и ошибок нет. Тройка и пятнадцать копеек выглядят подозрительно, но не мешают. А вот британские монеты до 1971 года ломают жадность: в ходу были пенни, монеты в 3 и 6 пенсов, шиллинг (12 пенсов), флорин (24) и полкроны (30), и на 48 пенсов жадный кассир отдаёт полкроны, шиллинг и шестипенсовик вместо двух флоринов.
Тенге, советские копейки и евро устроены так, что жадность не ошибается никогда; такие наборы монет называют каноническими. Британские монеты до перехода на десятичную систему и набор 1, 3, 4 — нет. Британия тут не одна: в Индии ходили монеты в 5, 10, 20 и 25 пайс, и 40 пайс жадный кассир отдавал тремя монетами (25, 10, 5) вместо двух двадцаток. Проверьте любой набор, который придёт в голову.
Вывод неприятный: жадное правило — всего лишь гипотеза. «Бери лучшее сейчас» на одних данных даёт оптимум, на других промахивается, и снаружи их не отличить. Нужен способ доказывать, что жадный шаг безопасен. Такой способ есть, и удобнее всего показать его на задаче попроще проводов.
Наряд второй: одна бригада
Электричество провели, теперь сеть надо обслуживать. В районе одна монтёрская бригада и одна машина с вышкой. Сёла присылают заявки: «отключите нам линию с 9 до 12, будем менять столбы». У каждой заявки своё окно, начать раньше или кончить позже нельзя, а бригада может быть только в одном месте. Все заявки не выполнить — окна пересекаются. Как выбрать, чтобы выполнить как можно больше?
Жадных правил напрашивается несколько. Брать самую короткую заявку: она меньше всего занимает бригаду. Брать ту, что начинается раньше всех: не терять утро. Брать ту, что мешает меньшему числу других. Или ту, что раньше всех кончается. Испытайте их.
Три правила из четырёх ломаются, и для двух из них вредные примеры несложные. Самая короткая заявка может задеть две длинные, которые друг другу не мешали. Самая ранняя может занять весь день. С правилом «меньше всего конфликтов» сложнее: вредный пример к нему — из одиннадцати заявок, но обмануть можно и его. А правило «раньше всех кончается» не ломается ни на каком примере. Это нужно доказать, и доказательство стоит запомнить: дальше оно повторится ещё не раз.
Отсортируем заявки по времени окончания и будем брать каждую, которая не пересекается с уже взятыми. Получится наибольшее возможное число заявок.
Пусть $g$ — заявка, которая кончается раньше всех. Возьмём любое наилучшее расписание и упорядочим его заявки по времени: $o_1, o_2, \ldots, o_k$. Заявка $g$ кончается не позже $o_1$, ведь раньше всех кончается именно она. Заменим в расписании $o_1$ на $g$. Конфликта не будет: $g$ кончается не позже $o_1$, а $o_1$ кончалась не позже, чем начиналась $o_2$. Заявок по-прежнему $k$, то есть получилось тоже наилучшее расписание — и оно начинается с жадного выбора.
Остальные заявки этого расписания, $o_2, \ldots, o_k$, начинаются после конца $g$ и составляют наилучшее расписание для тех заявок, что начинаются после конца $g$: будь среди них расписание длиннее, вместе с $g$ оно побило бы наилучшее. А жадный алгоритм после выбора $g$ тем же правилом решает как раз эту задачу, меньшую исходной. По индукции по числу заявок он находит в ней $k - 1$ заявку, а всего — $k$.
Этот приём называют аргументом обмена. Берём любое оптимальное решение и показываем, что его можно переделать — обменять кусок на жадный выбор — и не ухудшить. Значит, жадный шаг никогда не закрывает дорогу к оптимуму, а после него остаётся та же задача, только меньше. Вспомните кассу: для монет 1, 3, 4 и суммы 6 обмен не проходит. Единственный наилучший ответ — две тройки, и четвёрку, которую жадность взяла первой, в него не вставить.
Сама программа короче доказательства. Нажмите «Шаги» и следите за переменной free_at: она отмечает час, с которого бригада свободна.
Пять заявок из одиннадцати, и больше нельзя. Сортировка стоит $O(n \log n)$, проход по заявкам — $O(n)$. Нестрогий знак >= стоит нарочно: заявка, которая начинается в тот же час, когда кончилась предыдущая, допустима — будем считать, что бригада переезжает мгновенно. Окна в программе полуоткрытые, как range: заявка с 9 до 10 занимает час $[9, 10)$.
Остовное дерево
Вернёмся к проводам и скажем точно, что мы ищем. Сёла — вершины графа из главы 19, возможные провода — рёбра, и у каждого ребра есть вес: длина в километрах. Нужно выбрать часть рёбер так, чтобы по ним можно было добраться от любой вершины до любой, и чтобы сумма весов была наименьшей.
В наилучшем ответе не бывает круга. Если провода образуют цикл, выбросим из него любой провод: ток по-прежнему дойдёт куда угодно, в обход по оставшейся части круга, а провода стало меньше. Связный граф без циклов — это дерево, родственник деревьев из главы 17, только без корня и без деления на левых и правых. Поэтому ответ называют остовным деревом — деревом, на котором держатся все вершины, как на остове, — а самое лёгкое из таких деревьев минимальным остовным деревом. У дерева на $n$ вершинах ровно $n - 1$ ребро: сначала каждое село — отдельная сеть, их $n$; каждый провод без круга сливает две сети в одну; в конце сеть одна.
Краскал, Прим и Борувка из виджета действуют по-разному, но опираются на одно утверждение. Разделим сёла на две группы как угодно — например, на те, что западнее реки, и те, что восточнее. Такое деление называют разрезом, а провода, соединяющие группы, — рёбрами разреза. Хотя бы одно ребро разреза в сети обязано быть, иначе группы не связаны. Вопрос — какое.
Для любого разреза самое короткое ребро разреза входит хотя бы в одно минимальное остовное дерево.
Пусть $e$ — самое короткое ребро разреза, а $T$ — минимальное остовное дерево без $e$. Добавим $e$ к $T$. Между концами $e$ в дереве уже был путь, поэтому получится цикл, и только один: этот путь плюс $e$. Путь начинается на одной стороне разреза, а кончается на другой, значит, какое-то его ребро $f$ тоже пересекает разрез, и по выбору $e$ длина $f$ не меньше длины $e$. Выбросим $f$. Цикл разорван, а связность не потеряна: всё, что раньше шло через $f$, теперь можно обойти через $e$. Рёбер снова $n - 1$, значит, $T + e - f$ — остовное дерево, и оно не длиннее $T$. Это тоже минимальное остовное дерево, и в нём есть $e$.
Это снова аргумент обмена, теперь для проводов. Из леммы следует правота Краскала. Когда он берёт провод между сёлами $u$ и $v$, они лежат в разных сетях. Разрежем край так: сеть, в которой лежит $u$, против всех остальных сёл. Все провода короче уже рассмотрены, и ни один из них этот разрез не пересекает. Пересекай его какой-нибудь, концы такого провода лежали бы в разных сетях и сейчас, и тогда, когда до него дошла очередь: сети только растут. Краскал взял бы его, и концы оказались бы в одной сети. Значит, $u$ — $v$ — самое короткое ребро разреза, и по лемме его можно брать.
Кто с кем уже связан
В рецепте Краскала есть вопрос, который на карте мы решали глазами: не замкнёт ли провод круг? Иначе говоря, не лежат ли оба села уже в одной сети. Можно каждый раз обходить сеть в ширину, как в главе 19, но это $O(n)$ на каждый провод, а проводов в крае больше двухсот тысяч. Нужна структура данных, которая умеет два действия: сказать, в какой сети село, и слить две сети в одну.
Устроим её как армию. В каждой сети есть главное село, и каждое село помнит своего начальника; у главного начальник — оно само. Чтобы узнать, в какой сети село, идём по начальникам вверх, пока не дойдём до главного. Два села в одной сети, если главный у них один. Чтобы слить две сети, главный одной становится подчинённым главного другой — одно присваивание. Это система непересекающихся множеств, по-английски union-find — «объединить и найти». Живёт она в одном списке parent, как куча из главы 18 жила в одном массиве.
Цепочки начальников не должны вырастать длинными, и для этого есть две заплатки. Сливая сети, подчиняем меньшую большей: тогда путь от села до главного удлиняется, только когда его сеть хотя бы удваивается, и длиннее $\log_2 n$ не бывает. А поднимаясь к главному, сокращаем дорогу на будущее: каждое село по пути переподчиняем начальнику его начальника. Нажмите «Шаги» и следите за списком parent.
Провод 0—2 оказался лишним: сёла 0 и 2 уже связаны через 1 и 3. Последний провод, 3—7, сливает две сети по четыре села, и по дороге к главному путь села 3 сократился: было 3 → 2 → 0, стало 3 → 0. С обеими заплатками любая последовательность из $m$ операций над $n$ сёлами стоит $O(m\,\alpha(n))$, где $\alpha$ — обратная функция Аккермана. Для полного сжатия путей это доказал Роберт Тарьян в 1975 году, а для нашего, «через ступеньку», — он же вместе с Яном ван Леувеном в 1984-м. Растёт $\alpha$ так медленно, что для любого числа сёл, которое поместится в память любого компьютера, она не больше 4. Саму структуру описали Бернард Галлер и Майкл Фишер в 1964 году.
Вся Южная Моравия
Соберём из этих частей Краскала и запустим его на всём крае. В файле /data/greedy/moravia.csv — 675 городов и сёл Южноморавского края с координатами и числом жителей, по данным открытого справочника GeoNames (лицензия CC BY 4.0). Возможных проводов, каждый с каждым, — 227 475. Расстояние считаем по прямой; на таких расстояниях землю можно считать плоской, если не забыть, что градус долготы на широте Брно по длине — лишь $\cos 49^\circ \approx 0{,}66$ градуса широты.
Минимальное остовное дерево всего края — 1570,5 км. Если бы к каждому селу тянули свой провод из Брно, как лучи звезды, понадобилось бы 23 364 км, почти в пятнадцать раз больше. Самый длинный провод лучшей сети — 5,6 км, от центра Брно до Моравани: городские районы Брно в файл не вошли, и центру не к кому подключиться ближе. А вся работа заняла меньше секунды — большую часть времени Python вычислял и сортировал двести тысяч расстояний.
Прим: сеть растёт от станции
Краскал строит сеть кусками в разных концах края и только потом сшивает их. Инженеру привычнее иначе: есть электростанция, и сеть растёт от неё. На каждом шаге подключаем то село, которое ближе всего к уже построенной сети. Это тоже жадность, и правота её — та же лемма о разрезе: разрез «подключённые против остальных», и мы берём самое короткое его ребро.
Ближайшее село удобно доставать из кучи — снова очередь с приоритетом из главы 18. В куче лежат провода-кандидаты от сети к неподключённым сёлам. Когда село подключено, в куче могут остаться другие, более длинные провода к нему. Искать и удалять их из середины кучи долго, поэтому оставим их на месте и выбросим устаревший провод, когда он всплывёт наверх. Этот приём понадобится нам и в следующей главе.
Та же длина, 1570,5 км. Когда все длины различны, минимальное остовное дерево единственно, и оба алгоритма находят одно и то же дерево, только в разном порядке. Прим начинает с ближайших к Брно сёл — Моравани, Небовиды, Остоповице — и расползается по краю, как пятно. Здесь каждое подключённое село кладёт в кучу провода ко всем остальным, это $O(n^2 \log n)$. Если же линии разрешены только вдоль дорог и их $m$, то и Прим с кучей, и Краскал с сортировкой работают за $O(m \log n)$.
Алгоритм самого Борувки работает раундами. В каждом раунде все куски сети одновременно выбирают самый короткий провод, ведущий из куска наружу, и все эти провода прокладываются разом. Каждый кусок сливается хотя бы с одним соседом, поэтому кусков становится как минимум вдвое меньше, а раундов не больше $\log_2 n$. Правота — снова лемма о разрезе, по разрезу на каждый кусок. Внутри раунда куски друг от друга не зависят, и это удобно компьютерам со многими процессорами: на идее Борувки основаны многие параллельные алгоритмы для остовных деревьев. Раунды можно увидеть в виджете из начала главы, кнопка «Борувка».
Почему Борувка требовал, чтобы все расстояния были различны
Задачу он с самого начала поставил так, чтобы все взаимные расстояния между точками были различны, и без этого условия его алгоритм ломается. Пусть три куска сети стоят в вершинах равностороннего треугольника. Каждый выбирает самый короткий провод наружу, а они все одинаковые: первый может выбрать провод ко второму, второй — к третьему, третий — к первому. Проложив все три разом, получим круг. Лечится это так же, как ничьи в куче из главы 18: при равной длине сравниваем провода по номерам, и тогда «самый короткий» всегда определён однозначно. Краскалу и Приму равные длины не мешают: они берут по одному проводу и каждый раз проверяют, не замкнёт ли он круг.
Наряд третий: телеграммы
Когда сеть построена, по ней надо переговариваться: диспетчеру — с подстанциями, подстанциям — друг с другом. Каждый бит на линии стоит времени, а время — денег. В главе 8 мы считали, сколько тактов тратит азбука Морзе на «Войну и мир», и раздавали короткие коды частым буквам, а самый выгодный код по частотам обещали построить здесь. Его придумал студент, которому очень не хотелось сдавать экзамен.
Сначала — какие коды нам годятся. Азбука Морзе отделяет буквы паузами, а в двоичном коде пауз нет, только нули и единицы. Чтобы читать без разделителей, хватит одного правила: ни один код не должен быть началом другого. Такой код называют префиксным. Читаем биты по одному; как только набралось кодовое слово, это буква, и начинаем следующую. Префиксный код удобно рисовать деревом: из каждой развилки налево ветка 0, направо 1, буквы сидят в листьях, и код буквы — дорога к ней от корня. Раз буквы только в листьях, ни одна дорога не продолжает другую.
Цена кода — сумма по всем буквам: сколько раз буква встречается, умноженное на длину её кода, то есть на глубину листа. Хаффман заметил, где ошибиться нельзя, — внизу. Пусть $x$ и $y$ — две самые редкие буквы. Есть наилучшее дерево, в котором они братья на самом глубоком уровне. Это снова обмен: если редкая буква $x$ сидит выше более частой $a$, поменяем их местами, и цена изменится на $(f_a - f_x)(\ell_x - \ell_a) \le 0$, где $f$ — частоты, а $\ell$ — глубины. Теперь склеим братьев в одну «букву» с частотой $f_x + f_y$ — останется та же задача, только букв на одну меньше. Повторяем, пока не останется одно дерево. Получается код Хаффмана. Полное доказательство его оптимальности и того, почему средняя длина кода не бывает меньше энтропии, — в «Царице наук», в главе о мере информации; здесь нас интересует, как он устроен и что даёт на деле.
До Хаффмана лучшим считался способ сверху вниз, который называют кодом Шеннона — Фано: отсортировать буквы по частоте и разрезать список на две части с суммами как можно ближе; левой части — 0, правой — 1, и так в каждой части, пока не останутся одиночки. Это тоже жадность, но она принимает самое ответственное решение, наверху, первым — и ошибку потом не исправить. Пусть буквы встречаются 15, 7, 6, 6 и 5 раз. Сверху вниз: части $\{15, 7\}$ и $\{6, 6, 5\}$, коды 00, 01, 10, 110, 111 — всего 89 бит. Хаффман сливает $5 + 6$, потом $6 + 7$, потом $11 + 13$, потом $15 + 24$: у частой буквы код из одного бита, у остальных по три, всего 87. Хаффман начинал с того конца, где жадный шаг можно доказать, и в этом вся разница. Кнопка «Пример, где сверху хуже» в виджете загружает эти частоты.
Две самые редкие буквы, снова и снова, — работа для кучи из главы 18. В кучу кладём тройки: частота, номер, дерево. Номер разбивает ничьи, чтобы heapq не пытался сравнивать деревья. Дерево — либо буква, либо пара поддеревьев.
В романе 2 904 144 символа, разных — 165. Чтобы различать 165 знаков, равномерному коду нужно 8 бит на символ, а UTF-8 тратит на каждую русскую букву 16. Код Хаффмана — 4,86 бита на символ: на 39 % короче равномерного и почти втрое короче UTF-8. Пробел, самый частый знак, получил код из трёх бит, «о» — из четырёх, а «ё», которая встретилась в издании всего 99 раз, — из пятнадцати. Среди кодов, которые кодируют каждую букву отдельно, лучше не бывает, и до предела рукой подать: Шеннон доказал, что такой код не может тратить меньше энтропии, а она у «Войны и мира» 4,82 бита на символ. Чтобы сжать сильнее, кодируют уже слова и повторы, — об этом глава 47. Код Хаффмана там тоже будет: он работает внутри ZIP, PNG, JPEG и MP3, обычно в паре с другими приёмами.
Когда жадность права
Что общего у бригады, проводов и кода и чем от них отличается касса с монетами 1, 3, 4? Жадный алгоритм прав, когда выполнены два условия. Первое: жадный шаг безопасен — есть наилучшее решение, которое начинается с него. Это доказывают обменом: берут любое наилучшее решение и переделывают его под жадный выбор, не проигрывая. Второе: после жадного шага остаётся задача того же вида, только меньше, и её наилучший ответ вместе с жадным шагом даёт наилучший ответ на всю. Это та же оптимальная подструктура, на которой стоит динамическое программирование из главы 22.
Разница между двумя подходами — в том, сколько вариантов перебирать. Динамика на каждом шаге пробует все варианты и помнит лучшие ответы подзадач. Жадность выбирает один вариант и не оглядывается. Когда жадность права, она проще и быстрее: заявки выбираются одним проходом, без таблицы. Когда не права, нужна динамика. С монетами 1, 3, 4 нарушено первое условие: ни одно наилучшее решение для суммы 6 не начинается с четвёрки.
Граница хорошо видна на рюкзаке. В главе 22 вор брал вещи целиком, и правило «сначала самое дорогое за килограмм» там ошибается. Но если товар можно отсыпать — зерно, песок, специи, — то же правило право: насыпаем самый дорогой за килограмм, пока он не кончится или рюкзак не заполнится, потом следующий. Обмен доказывает это в одну строчку: любой килограмм дешёвого товара в рюкзаке можно заменить килограммом более дорогого, оставшегося снаружи, и рюкзак не подешевеет.
В какой из задач жадный алгоритм всегда находит наилучший ответ?
Заправки — та же бригада. Возьмём любой наилучший план остановок и сравним его первую остановку с жадной. Жадная не ближе к старту: дальше на одном баке не уехать. Заменим первую остановку плана на жадную — от неё до второй остановки плана не дальше, чем было, бака хватит. Остановок столько же, а дальше — та же задача от новой точки.
Матроиды: когда жадность права при любых весах
Есть теория, которая отвечает на вопрос «когда жадность права» сразу для целого класса задач. Назовём набор проводов допустимым, если в нём нет круга. У допустимых наборов два свойства. Часть допустимого набора допустима. И меньший допустимый набор всегда можно дополнить чем-то из большего: если в одном наборе без кругов проводов меньше, чем в другом, то какой-то провод второго можно добавить к первому, не замкнув круга. Структуры с такими свойствами Хасслер Уитни в 1935 году назвал матроидами. Теорема, которую связывают с именами Ричарда Радо и Джека Эдмондса, говорит: жадный алгоритм «бери самый выгодный элемент, если набор остаётся допустимым» находит наилучший набор при любых весах тогда и только тогда, когда допустимые наборы образуют матроид. Краскал — её частный случай. Выбор заявок — не матроид, и жадность там права только при особом порядке: по времени окончания.
И последнее. Даже когда жадность не находит оптимум, она часто быстро даёт неплохой ответ. Коммивояжёр, который всегда едет в ближайший непосещённый город, проезжает больше лучшего маршрута, но обычно на десятки процентов, а не в разы. Насколько именно и почему точный ответ так трудно получить — разговор главы 58.
Задачи
Четыре задачи — четыре жадных алгоритма главы. В каждой есть тест на большом входе с секундомером, а в каждой второй — подвох на крае.
Заявки заданы парами (start, end) — полуоткрытые окна $[start, end)$, всегда start < end. Напишите max_requests(requests), которая возвращает список выбранных заявок (самих пар) в порядке времени: выбранные окна не пересекаются, а заявок в списке наибольшее возможное число. Заявка, которая начинается в момент конца другой, с ней не пересекается. Время — любые числа, бывают и отрицательные, и дробные. Одинаковые заявки бывают — выполнить можно только одну из них. В тестах до 200 000 заявок.
Отсортируйте заявки по времени окончания: sorted(requests, key=lambda r: r[1]).
Помните, с какого момента бригада свободна. Заявка подходит, если начинается не раньше этого момента.
Начальное значение float("-inf"), а не 0: время в тестах бывает отрицательным. Выбранные заявки уже идут по времени — по концам, а значит, и по началам, ведь они не пересекаются. Правота — теорема из раздела о бригаде.
Напишите класс DisjointSets: DisjointSets(n) создаёт $n$ сёл с номерами от 0 до $n - 1$, каждое в своей сети. Методы: find(x) возвращает главное село сети, где лежит x (у сёл одной сети — одно и то же); union(a, b) сливает сети сёл a и b и возвращает True, а если они уже в одной сети — ничего не меняет и возвращает False. Атрибут groups — сколько сейчас отдельных сетей. В тестах — сотни тысяч операций, и цепочка начальников без заплаток вытянется в линию.
Возьмите find и union из ячейки «сети.py» и сделайте их методами: parent и size — атрибуты объекта.
Не забудьте уменьшать groups при каждом удачном слиянии. Рекурсивный find на цепочке в 200 000 сёл упрётся в предел глубины рекурсии — пишите циклом.
Хватило бы и одной заплатки: только подвешивание меньшей к большей даёт $O(\log n)$ на операцию, только сжатие путей — амортизированно тоже $O(\log n)$. Обе вместе дают почти константу.
Сёла пронумерованы от 0 до $n - 1$ ($n \ge 1$), возможные провода заданы тройками (u, v, w): между сёлами u и v, длина w (бывает и отрицательной — скажем, за линию доплачивает государство). Напишите kruskal(n, edges), которая возвращает пару: общую длину минимального остовного дерева и список его проводов — тех же троек, что во входе. Если связать все сёла нельзя, верните None. Между двумя сёлами бывает несколько проводов, а бывает и «провод» из села в само себя.
Сортируйте тройки по длине: sorted(edges, key=lambda e: e[2]). Для проверки «не замкнёт ли круг» нужна система непересекающихся множеств — из прошлой задачи или попроще, на одном списке.
Провод из села в само себя всегда замыкает круг — find это заметит сам. Все сёла связаны, если проводов в дереве набралось $n - 1$.
Здесь только сжатие путей, без подвешивания по размеру, — для Краскала этого хватает с запасом. Отрицательные длины алгоритму не мешают: лемма о разрезе нигде не пользуется тем, что длины положительны.
Напишите huffman_code(text), которая возвращает словарь: каждому символу текста — его код, строку из '0' и '1'. Код должен быть префиксным, а длина закодированного текста — наименьшей возможной. Если в тексте всего один различный символ, его код — один бит. Для пустого текста верните пустой словарь. Тесты прогонят и всю «Войну и мир».
Положите в кучу тройки (частота, номер, дерево), где дерево — символ. Пока в куче больше одного дерева, доставайте два и кладите их пару с суммой частот и новым номером.
Коды раздайте обходом готового дерева: налево — '0', направо — '1'. Если дерево — один символ, его код '0', иначе он получит пустую строку.
Номер в тройке нужен, чтобы при равных частотах heapq не сравнивал символ с кортежем — это TypeError. Коды раздаются обходом со стеком, как в главе 15, но годится и рекурсия: глубоким дерево не бывает. Чтобы оно вытянулось в линию из $k$ развилок, частоты должны расти как числа Фибоначчи, и уже для $k = 40$ понадобился бы текст в сотни миллионов символов.
Куда дальше
В 1959 году Дейкстра отправил в новый журнал Numerische Mathematik заметку на три страницы — «Заметка о двух задачах, связанных с графами». Первая задача в ней наша: соединить точки так, чтобы общая длина связей была наименьшей. Вторая — найти между двумя точками кратчайший путь. В Моравии провода проложены, но инженеру теперь нужно ездить: из Брно на аварию в Микулов, оттуда на подстанцию. Перебирать все дороги бессмысленно, их слишком много, а BFS из главы 19 считает перекрёстки, а не километры. Нужен самый короткий путь из A в B. Следующая глава соберёт навигатор и проложит маршрут по настоящему графу московского метро. А алгоритм для него Дейкстра, как он сам рассказывал, придумал за двадцать минут — за чашкой кофе на террасе амстердамского кафе.