Минимальный размер контейнера для перевозки пакетов за D дней

Источник: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days

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

i-й пакет на конвейерной ленте имеет вес weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, указанном в массиве с весом). Мы не можем загрузить больше веса, чем максимальная грузоподъемность корабля.

Подсчитать наименьшую грузоподъемность корабля, при которой все посылки на конвейерной ленте будут отправлены в течение дней дней. 

Пример 1:

Дано: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Результат: 15
Пояснение: Минимальная вместимость корабля = 15, чтобы отправить все пакетыза 5 дней по схеме:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Обратите внимание, что груз должен быть отправлен в том порядке, в котором он появляется в массиве weights, поэтому вариант 14, когда мы разделяем партии по схеме (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) не подходит.

Пример 2:

Дано: weights = [3,2,2,4,1,4], days = 3
Результат: 6
Пояснение: Минимальная вместимость корабля = 6, чтобы отправить все пакетыза 3 дня по схеме:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Пример 3:

Дано: weights = [1,2,3,1,1], days = 4
Результат: 3
Пояснение:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

 

Ограничения:

• 1 <= дни <= weights.length <= 5 * 104
• 1 <= weights[i] <= 500 

Решение такое же, как и в задаче на минимизацию максимальной суммы

 

class Solution {
     public int shipWithinDays(int[] weights, int D) {
        if (weights == null || weights.length == 0) {
            return 0;
        }
        int start = Integer.MIN_VALUE;
        int end = 0;
        for (int x : weights) {
            start = Math.max(start, x);
            end += x;
        }
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (check(weights, D, mid)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
    
    private boolean check(int[] weights, int D, int cap) {
        int sum = 0, days = 1;
        for (int x : weights) {
            if (sum + x > cap) {
                sum = x;
                days++;
                if (days > D) {
                    return false;
                }
            } else {
                sum += x;
            }
        }
        return days <= D;
    }
}