NeetCode #277LC-1011MediumBinary SearchNC 250
← Back to All Problems#277 · #1011 · Capacity To Ship Packages Within D Days(在 D 天内送达包裹的能力)
📌 Problem Statement & Constraints
A conveyor belt has packages with weights
weights[i] that must be shipped within days days, in the given order. Each day a ship carries packages in order until the weight limit is reached. Return the minimum ship capacity. Constraints: 1 <= days <= weights.length <= 5 * 10^4, 1 <= weights[i] <= 500.💡 Core Algorithmic Approaches
- Binary search on the capacity. The predicate "can ship within
daysdays with capacityc" is monotone. - The lower bound is
max(weights), since a single package must fit; the upper bound issum(weights), which ships everything in one day. - For a given capacity, greedily fill each day and count the days used.
- Use
hi = midwhen feasible, sincemidmay itself be the answer.
💻 Benchmark Python3 Implementation
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
used = 1 # days needed at capacity mid
cur = 0
for w in weights:
if cur + w > mid:
used += 1 # start a new day
cur = 0
cur += w
if used <= days:
hi = mid # feasible -> try smaller
else:
lo = mid + 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log(sum(weights))): each predicate is O(n) and there are O(log V) of them.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Setting the lower bound to 1: a capacity below
max(weights)can never work, so the search would waste iterations (and the greedy would still count correctly, but the range is tighter withmax). - Using
hi = mid - 1when feasible: could skip the optimum; usehi = mid. - Forgetting that the order is fixed: packages must be shipped in order, which is what makes the greedy day-filling valid. Sorting would break the problem.
- Counting days as
ceil(sum / mid): the order and indivisibility of packages make the actual count larger.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.