⚡Flashcard Drill➔
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

  1. Binary search on the capacity. The predicate "can ship within days days with capacity c" is monotone.
  2. The lower bound is max(weights), since a single package must fit; the upper bound is sum(weights), which ships everything in one day.
  3. For a given capacity, greedily fill each day and count the days used.
  4. Use hi = mid when feasible, since mid may 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 with max).
  • Using hi = mid - 1 when feasible: could skip the optimum; use hi = 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems