# 1011. Capacity To Ship Packages Within D Days    • Time: $O(n\log(\Sigma |\texttt{piles[i]}|))$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public: int shipWithinDays(vector& weights, int days) { int l = *max_element(weights.begin(), weights.end()); int r = accumulate(weights.begin(), weights.end(), 0); while (l < r) { const int m = (l + r) / 2; if (shipDays(weights, m) <= days) r = m; else l = m + 1; } return l; } private: int shipDays(const vector& weights, int shipCapacity) { int days = 1; int capacity = 0; for (const int weight : weights) if (capacity + weight > shipCapacity) { ++days; capacity = weight; } else { capacity += weight; } return days; }; }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public int shipWithinDays(int[] weights, int days) { int l = Arrays.stream(weights).max().getAsInt(); int r = Arrays.stream(weights).sum(); while (l < r) { final int m = (l + r) / 2; if (shipDays(weights, m) <= days) r = m; else l = m + 1; } return l; } private int shipDays(int[] weights, int shipCapacity) { int days = 1; int capacity = 0; for (final int weight : weights) if (capacity + weight > shipCapacity) { ++days; capacity = weight; } else { capacity += weight; } return days; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: def canShip(shipCapacity: int) -> bool: shipDays = 1 capacity = 0 for weight in weights: if capacity + weight > shipCapacity: shipDays += 1 capacity = weight else: capacity += weight return shipDays <= days l = max(weights) r = sum(weights) return bisect.bisect_left(range(l, r), True, key=lambda m: canShip(m)) + l