# 1011. Capacity To Ship Packages Within D Days

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Capacity To Ship Packages Within D Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/1011-capacity-to-ship-packages-within-d-days)

A conveyor belt has **packages that must be shipped from one port to another within `days` days.**

The `ith` package on the conveyor belt has a weight of `weights[i]`. Each day, we load the ship with packages on the conveyor belt (in the order given by `weights`). We **may not load more weight than the maximum weight capacity of the ship.**

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within `days` days.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `1 <= days <= weights.length <= 5 * 10^4`
* `1 <= weights[i] <= 500`

```
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
  1st day: 1, 2, 3, 4, 5
  2nd day: 6, 7
  3rd day: 8
  4th day: 9
  5th day: 10

Note that the cargo must be shipped in the order given, 
so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
**Binary Search** Problem\
Find a **minimum capacity that can ship packages within certain days.**
{% endhint %}

#### **Boundary / Search Space**

> Left (Minimum) = MAX weights **(cannot seperate a single package)**\
> Right (Maximum) = TOTAL weights

#### **Condition**

> While Loop = Left < Right

#### **Return Value**

> Left
> {% endtab %}
> {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        
        # ==================================================
        #  Binary Search                                   =
        # ==================================================
        # time  : O(nlog(m)), m is the search space
        # space : O(1)
        
        maxWeight, total = 0, 0
        for w in weights:
            total += w
            maxWeight = max(maxWeight, w)
        
        l, r = maxWeight, total
        while l < r:
            capacity = (l + r) // 2
            if self.valid(weights, days, capacity): r = capacity
            else: l = capacity + 1
            
        return l
    
    def valid(self, weights: List[int], D: int, capacity: int) -> bool:
        days, total = 1, 0
        for w in weights:
            total += w
            if total > capacity:
                total = w
                days += 1
                
                if days > D: return False
                
        return True
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(nlog(m)), m is the search space
     * @space : O(1)
     */
    
    public int shipWithinDays(int[] weights, int days) {
        int l = 0, r = 0;
        for (int w: weights) {
            l = Math.max(l, w);
            r += w;
        }
        
        while(l < r) {
            int capacity = (l + r) / 2;
                
            int tmpDays = 1, tmpWeight = 0;
            for(int w: weights) {
                tmpWeight += w;
                if(tmpWeight > capacity) {
                    tmpWeight = w;
                    tmpDays += 1;
                    
                    if(tmpDays > days) break;
                }
            }
            
            if(tmpDays <= days) r = capacity;
            else l = capacity + 1;
        }
        
        return l;
    }
}
```

{% endtab %}
{% endtabs %}