Угадать ответ и бинарно искать саму догадку

У тебя очередь задач с длительностями [7, 2, 5, 10, 8] часов и 2 работника. Очередь нужно разрезать на 2 куска, не меняя порядок задач, и отдать по куску каждому работнику. Ты хочешь, чтобы рабочий день самого загруженного работника был как можно короче.

Отсортированного массива, в котором можно искать, здесь нет. Вопрос звучит так: какую самую короткую «самую длинную смену» можно получить? Перебор всех способов разрезать очередь быстро становится огромным, когда задач много.

Зато на другой вопрос ответить легко: «можно ли разрезать так, чтобы ни одна смена не была длиннее 18 часов?». Это проверка «да/нет», и она делается одним проходом по задачам. Пределы идут по порядку: если подходит 18, то подходят и 19, и 20, и любое большее число. Этого порядка хватает, чтобы искать сам ответ бинарным поиском.

Попробуй на задачах [7, 2, 5, 10, 8] предел 15 часов на одного работника. Первый берёт 7, 2 и 5, это 14 часов. Задача на 10 часов к нему уже не влезет, её берёт второй. Задача на 8 часов не влезет и ко второму: 10 + 8 = 18. Нужен третий работник, а их всего два. Значит, 15 не подходит.

Теперь предел 21. Первый берёт 7, 2 и 5 (14 часов), второй берёт 10 и 8 (18 часов). Двух работников хватило, 21 подходит.

Значит, ответ больше 15 и не больше 21. Дальше ты делишь этот промежуток пополам, как в обычном бинарном поиске. Предел не подошёл, бери больше. Подошёл, пробуй меньше. Через несколько проверок останется самый маленький предел, который ещё подходит. Здесь это 18.

Напиши проверку «влезает ли». Выбери cap, наибольшую сумму, которую разрешено набрать одному куску. Спроси, можно ли разрезать очередь на k кусков так, чтобы каждый уложился в этот предел. Проверка жадная. Идёшь по задачам и считаешь сумму текущего куска. Если следующая задача выведет сумму за cap, начинаешь новый кусок. В конце считаешь куски. Если их k или меньше, этот cap подходит. Назови эту проверку feasible(cap).

Проверка монотонная: при большем cap кусков никогда не нужно больше. Поэтому, если какой-то cap подошёл, подходит и любой больший. Получается та же картина false, false, ..., true, true, что в поиске границы. Разница в том, что теперь ты ищешь среди возможных значений ответа, а не среди позиций массива.

Задай границы поиска. Ответ не может быть меньше самой длинной задачи: одна задача целиком должна влезть в свой кусок. Поэтому lo = max(nums). И ответ не может быть больше суммы всех задач, когда всё лежит в одном куске. Поэтому hi = sum(nums). Дальше запусти поиск границы из урока 30 на промежутке от lo до hi. Проверь средний cap. Если он подходит, задай hi = mid. Если нет, задай lo = mid + 1. В конце верни lo.

Проследим на [7, 2, 5, 10, 8], k = 2. Границы: lo = 10 (самая длинная задача), hi = 32 (сумма всех).

• Середина 21. Куски 7 + 2 + 5 = 14 и 10 + 8 = 18, всего 2. Подходит, поэтому hi = 21.
• Середина (10 + 21) >> 1 = 15. Куски 14, 10 и 8, всего 3. Не подходит, поэтому lo = 16.
• Середина (16 + 21) >> 1 = 18. Куски 14 и 18, всего 2. Подходит, поэтому hi = 18.
• Середина (16 + 18) >> 1 = 17. Куски 14, 10 и 8, всего 3. Не подходит, поэтому lo = 18.
• lo и hi сошлись на 18. Ответ 18.

Время: O(n · log(range)). Бинарный поиск делает около log(range) шагов, и на каждом шаге один проход проверки за O(n). Здесь log берётся от размаха возможных ответов (sum - max), а не от длины массива. Для примера урока размах 32 - 10 = 22, и шагов понадобилось 4. Память: O(1) сверх входа.

Найти разбиение можно и динамическим программированием (решение строится из ответов на меньшие подзадачи). Но написать его без ошибок обычно труднее. Монотонная проверка «да/нет» и поиск по ответу проще, и в них сложнее ошибиться.

Балансировка нагрузки и выбор размера шардов (частей, на которые делят данные между серверами): работу режут так, чтобы самый загруженный сервер не вышел за предел. Планирование вида «отправить все посылки за D дней». Настройка ограничений скорости. Задача вида «Коко ест бананы» с собеседований: найти наименьшую скорость, при которой работа успевает к сроку. Выбор самой маленькой машины, которая ещё выполняет SLA (обещанный клиенту уровень сервиса). У git bisect та же форма: ответ это первый плохой коммит, а isBad(commit) даёт монотонную проверку на промежутке коммитов вместо значений нагрузки.