# 1011. Capacity To Ship Packages Within D Days
#### Difficulty: Medium
link: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

### 1. Binary Search
#### $O(n\ log\ m)$ runtime, $O(1)$ space
###### n = len(weights), m = sum(weights)

找一個最小值來滿足題目要求，不想一個個慢慢嘗試，就用效率較高的Binary search。

搜尋範圍的下界是max(weights)，確保船一定裝得下每一個貨品；上界是sum(weights)，一天能裝完所有貨品的情況。

shipping_days函數計算，在給定船的capacity的情況，總共需要多少天來運送。Binary Search會找出滿足題目要求(i.e. 天數<=days)的最小capacity。

##### python

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def shipping_days(capacity):
            count, total = 0, 0
            for w in weights:
                if total + w > capacity:
                    total = 0
                    count += 1
                total += w
            
            return count + 1
        
        left, right = max(weights), sum(weights)
        while left < right:
            mid = left + (right - left) // 2
            if shipping_days(mid) <= days:
                right = mid
            else:
                left = mid + 1
        
        return left

###### tags: `leetcode`