Сложность: medium
На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней.
Пример:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
👨💻 Алгоритм:
1⃣Определение диапазона возможных ответов:
Минимальная грузоподъемность должна быть не меньше максимального веса одного пакета (чтобы хотя бы один пакет можно было загрузить).
Максимальная грузоподъемность - это сумма всех весов (если все пакеты будут отправлены за один день).
2⃣Использование бинарного поиска:
Примените бинарный поиск в диапазоне от минимальной до максимальной грузоподъемности, чтобы найти наименьшую грузоподъемность, при которой все пакеты можно отправить за заданное количество дней.
3⃣Проверка возможности отправки всех пакетов за заданное количество дней:
Напишите вспомогательную функцию, которая проверяет, можно ли отправить все пакеты при заданной грузоподъемности за определенное количество дней. Эта функция проходит по списку весов и считает количество необходимых дней для отправки всех пакетов при текущей грузоподъемности.
😎 Решение:
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
def canShipInDays(capacity):
days = 1
total = 0
for weight in weights:
if total + weight > capacity:
days += 1
total = 0
total += weight
return days <= D
left, right = max(weights), sum(weights)
while left < right:
mid = (left + right) // 2
if canShipInDays(mid):
right = mid
else:
left = mid + 1
return left
Ставь 👍 и забирай 📚 Базу знаний