Задача с собеседования в eBay

Задача с собеседования в eBay Коко любит есть бананы. Имеется n куч бананов, где i-я куча содержит piles[i] бананов. Охранники ушли и вернутся через h часов. Коко может выбрать скорость поедания бананов в час (равняется k). Каждый час она выбирает какую-либо кучу и съедает k бананов из неё. Если в выбранной куче меньше k бананов, она съедает их все и в течение этого часа больше не ест. Коко любит есть медленно, но хочет успеть съесть все бананы до возвращения охранников. Верните минимальное целое число k, при котором Коко сможет съесть все бананы в течение h часов. Пример 1: Input: piles = [3,6,7,11], h = 8 Output: 4 Пример 2: Input: piles = [30,11,23,4,20], h = 5 Output: 30 Пример 3: Input: piles = [30,11,23,4,20], h = 6 Output: 23 Ограничения: 1 <= piles.length <= 10⁴ piles.length <= h <= 10⁹ 1 <= piles[i] <= 10⁹ НАШ ЧАТ АЛГОРИТМИСТОВ Решение Используем бинарный поиск, а точнее бинарный поиск по ответу : если Коко успеет съесть все бананы при некоторой скорости k, значит, она сможет их съесть и при любой скорости больше k (свойство монотонности). Таким образом, можно отбросить половину диапазона поиска. В отличие от классического бинпоиска здесь не требуется сортировка входных данных, так как искать результат будем не в массиве piles, а в уже упорядоченном диапазоне скоростей (левую границу определим как 1, а правую - как max(piles)). Порядок самих куч не влияет на сумму часов. - Определяем исходный диапазон поиска: l = 1 (минимальная возможная скорость), r = max(piles) (кол-во бананов в самой большой куче, так как в любом случае нельзя съесть кучу быстрее, чем за час); - Задаём условие для перехода в левую или правую половину: в цикле бинарного поиска вычисляем среднюю скорость. Проходим по всем кучам и считаем кол-во часов, за которые Коко съест все бананы при текущем гипотетическом значении k: hours += (p + k - 1) // k Формула вычисления часов работает следующим образом: к примеру, Коко успевает съесть за час все бананы из кучи, кроме 1. На этот 1 банан в любом случае нужен 1 дополнительный час, в течение которого Коко съест только его, не начиная новую кучу. То есть нам требуется округление вверх (целочисленное деление в питоне по умолчанию округляет вниз). Нужно добавить такое кол-во бананов, чтобы и получить необходимый дополнительный час при наличии остатка, и корректно обработать числа без остатка. Значение, которое сработает в любом из двух случаев - это прибавка k - 1 (максимальное значение, не создающее дополнительные часы, когда у нас нет остатка). Предположим, p = 11, а k = 5. При простом делении p // k получили бы 2, и один банан остался бы без учёта при подсчёте часов. Но если пользуемся формулой (11 + 5 -1) // 5, получаем 3 часа, которые потребуются, чтобы съесть 11 бананов со скоростью 5 бананов/час. А если бы в другой куче было 15 бананов, которые делятся на 5 без остатка, формула тоже сработала бы: (15 + 5 - 1) // 5 = 3 (всё те же 3 часа, так как целочисленное деление просто отбросит остаток 4); - Сдвигаем границы поиска: Если Коко успевает съесть все бананы: запоминаем k как текущего кандидата, обновляя res, и сдвигаем правую границу поиска влево (пытаемся найти ещё меньшую скорость); Если не успевает: сдвигаем левую границу вправо, так как нужно искать среди больших скоростей; Возвращаем минимальную возможную скорость, при которой Коко сможет съесть все бананы, уложившись в h часов. Сложность O(n log m) - по времени (где n - кол-во куч бананов, а m - максимальное кол-во бананов в куче) O(1) - по памяти (храним только переменные, не создавая дополнительных структур данных) Код class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: l, r = 1, max(piles) res = r while l <= r: k = (l + r) // 2 hours = 0 for p in piles: hours += (p + k - 1) // k if hours <= h: res = min(res, k) r = k - 1 else: l = k + 1 return res @algoses