#1011

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Capacity To Ship Packages Within D Days

Find the minimum ship capacity needed to ship all packages within D days, ensuring the cargo is shipped in the given order.

array binary search

Problem Statement

You are tasked with shipping packages on a conveyor belt from one port to another within a given number of days. Each package on the conveyor belt has a weight represented by the list weights[]. The goal is to load a ship with packages in the order provided, ensuring no day exceeds the maximum weight capacity of the ship. You must determine the least possible weight capacity that allows you to ship all the packages within the given days.

The ship's loading process is such that no day can exceed the specified capacity, and the cargo must be shipped in the given order. You need to minimize the weight capacity, ensuring that all packages are delivered within the required time frame.

Examples

Example 1

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5

Output: 15

A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1, 2, 3, 4, 5 2nd day: 6, 7 3rd day: 8 4th day: 9 5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2

Input: weights = [3,2,2,4,1,4], days = 3

Output: 6

A ship capacity of 6 is the minimum to ship all the packages in 3 days like this: 1st day: 3, 2 2nd day: 2, 4 3rd day: 1, 4

Example 3

Input: weights = [1,2,3,1,1], days = 4

Output: 3

1st day: 1 2nd day: 2 3rd day: 3 4th day: 1, 1

Constraints

1 <= days <= weights.length <= 5 * 104
1 <= weights[i] <= 500

Solution Approach

Binary Search on Capacity

The key idea is to perform binary search over the range of possible capacities. The lower bound is the maximum weight of a single package, and the upper bound is the sum of all the package weights. The binary search will help minimize the capacity while ensuring the packages can be shipped in the required days.

Checking Feasibility

For each midpoint value during the binary search, use a helper function possible(capacity) to check if it's feasible to ship the packages within the given days using that capacity. If it is, try a smaller capacity; otherwise, increase the capacity.

Greedy Packing Strategy

The greedy strategy is used to simulate the shipping process. Starting from the first package, pack the ship until adding another package exceeds the current capacity. If it does, start a new day, keeping track of the number of days used, and ensure it does not exceed the allowed days.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n * log(S)), where n is the number of packages and S is the sum of all weights. The binary search takes O(log(S)) iterations, and for each iteration, we check if shipping is feasible with a linear pass through the array, resulting in a total time complexity of O(n * log(S)). The space complexity is O(1), as we only use a constant amount of extra space.

What Interviewers Usually Probe

Candidate demonstrates understanding of binary search on the answer space.
Candidate uses a greedy strategy to pack the ship while maintaining the required days.
Candidate effectively handles the edge cases, like the smallest and largest possible capacities.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly implement the binary search bounds, which could lead to an incorrect answer.
Misunderstanding the greedy strategy and incorrectly packing packages, resulting in more days than allowed.
Overcomplicating the solution or missing optimization opportunities by not using binary search efficiently.

Follow-up variants

Adjust the problem to allow packages to be loaded in any order, requiring a different optimization approach.
Change the constraints to allow multiple ships to be used, altering the solution's complexity and strategy.
Introduce a variable number of days and see if the approach can handle dynamic adjustments.

FAQ

How do I apply binary search in the Capacity To Ship Packages Within D Days problem?

Apply binary search over the possible ship capacities, starting from the maximum weight of a single package and going up to the sum of all weights. At each step, check if it's possible to ship within the given days with the current capacity.

What is the greedy strategy used in this problem?

The greedy strategy involves packing the ship day by day, adding packages to the ship until the total weight exceeds the current capacity. When it does, a new day starts.

What should I watch out for when implementing binary search in this problem?

Ensure the binary search bounds are correctly set and that you handle the logic for checking feasibility efficiently. Avoid off-by-one errors when determining whether a capacity can fit within the allowed days.

How does GhostInterview help with preparing for this problem?

GhostInterview provides targeted practice and hints related to binary search, helping you optimize your solution and understand key problem-solving techniques.

What is the time complexity of the solution?

The time complexity is O(n * log(S)), where n is the number of packages, and S is the sum of all weights. This is due to the binary search and the linear scan required to check feasibility.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def check(mx):
            ws, cnt = 0, 1
            for w in weights:
                ws += w
                if ws > mx:
                    cnt += 1
                    ws = w
            return cnt <= days

        left, right = max(weights), sum(weights) + 1
        return left + bisect_left(range(left, right), True, key=check)

Continue Practicing

#1004 max consecutive ones iii #1027 longest arithmetic subsequence #1095 find in mountain array