Practice/Meta/Leetcode 1011. Capacity To Ship Packages Within D Days

Leetcode 1011. Capacity To Ship Packages Within D Days

CodingMust

Problem

A warehouse needs to ship packages in a specific order over a given number of days. Each day, the warehouse can load packages onto a truck with a fixed weight capacity. Packages must be shipped in the exact order they appear in the array—you cannot rearrange them.

Your task is to determine the minimum truck capacity (maximum weight the truck can carry) needed to ship all packages within the given number of days.

Requirements

1. Packages must be shipped in the order they appear in the input array
2. Each day, you load consecutive packages until adding another would exceed the truck's capacity
3. Find the smallest possible truck capacity that allows shipping all packages within the given days
4. Every package must be shippable (capacity must be at least as large as the heaviest package)

Constraints

• 1 ≤ days ≤ packages.length ≤ 50,000
• 1 ≤ packages[i] ≤ 500
• Time complexity should be O(n log(sum)) where n is the number of packages
• Space complexity should be O(1)

Examples

Example 1:

Input: packages = [1, 2, 3, 4, 5], days = 5 Output: 5 Explanation: We can ship one package per day with capacity 5: Day 1: [1] Day 2: [2] Day 3: [3] Day 4: [4] Day 5: [5]

Example 2:

Input: packages = [3, 2, 2, 4, 1, 4], days = 3 Output: 6 Explanation: With capacity 6, we can ship in 3 days: Day 1: [3, 2] (total weight = 5) Day 2: [2, 4] (total weight = 6) Day 3: [1, 4] (total weight = 5) We cannot use capacity 5 because [2, 4] would exceed it.

Example 3:

Input: packages = [1, 2, 3, 1, 1], days = 4 Output: 3 Explanation: With capacity 3: Day 1: [1, 2] (total = 3) Day 2: [3] (total = 3) Day 3: [1, 1] (total = 2) We use 3 days, which is within our limit of 4.