1011. Capacity To Ship Packages Within D Days
Problem Description
In this problem, we are tasked with finding the minimum weight capacity of a ship that is required to ship all packages on a conveyor belt within a specified number of days. Each package has a certain weight, and the ship cannot carry more than its maximum weight capacity. Therefore, the goal is to determine the smallest maximum weight that the ship can handle such that all the packages can still be shipped on time.
To accomplish this task, the packages must be loaded onto the ship in the same order as they are placed on the conveyor belt. This restriction adds complexity since we cannot reorder the packages to better fit the ship's weight capacity on a given day. Additionally, there is a limit to the number of days available to ship all packages.
Put simply, we need to discover the lightest possible maximum weight of the ship that allows all packages to be shipped within the given time frame. This weight determines how many packages can be loaded each day without exceeding the ship's weight limit, thus ensuring timely delivery.
Intuition
The solution to this problem relies on binary search, an efficient algorithm for finding an item in a sorted array. However, the direct application is not obvious because the weights are not sorted, and we are also dealing with an optimization problem, not just a simple search.
We use binary search to narrow down the possible range of the ship's weight capacity. The intuition here is that there is a lower bound, which is at least as large as the heaviest package (since the ship must be able to carry the heaviest package), and an upper bound, which is the sum of all package weights (since the ship can carry all packages at once).
The binary search will repeatedly split the range in half. At each step, it will guess a middle value and use a helper function check
to determine if it is possible to ship all packages within 'days' days, without exceeding the guess weight capacity. The helper function will simulate the process of loading packages onto the ship:
- It sums the weights of the packages until adding another package would exceed the assumed maximum capacity.
- When the maximum is reached, it simulates the start of a new day, incrementing a day counter.
- If the day counter exceeds the allowed number of days, the guess is too low and we must try a larger capacity.
The binary search is constrained within the range between the heaviest package and the total weight using the bisect_left
function. bisect_left
will find the position to insert the lower bound of the ship's capacity in such a way that all packages are shipped within the time frame. At the end of the binary search, the minimum weight capacity of the ship is found, which is the goal of the problem.
Learn more about Binary Search patterns.
Solution Approach
The solution approach revolves around binary search, and here's a step-by-step breakdown of how the provided solution in Python implements it:
-
Define the
check
Function:- The helper function
check(mx)
simulates the loading of packages onto the ship to determine if it is possible to ship all packages withindays
days, given a maximum shipping weight ofmx
. - It iterates through each weight in
weights
and aggregates them until the current load exceedsmx
. - Once the aggregated weight exceeds
mx
, it simulates starting a new day by resetting the load to the current weight and incrementing the day count. - After iterating through all weights, if the number of days needed is less than or equal to
days
, it means themx
is a viable capacity; otherwise, it is not.
- The helper function
-
Determine the Search Range:
- The lower bound
left
is set to the maximum single package weight (max(weights)
). This is the absolute minimum capacity the ship must have to ensure even the heaviest package can be shipped. - The upper bound
right
is set to the sum of all weights plus one (sum(weights) + 1
), the plus one being a non-inclusive upper bound for the binary search.
- The lower bound
-
Perform Binary Search:
bisect_left
function is used to perform the binary search. This is a function provided by Python's standard library, which uses binary search to find the insertion point for a given elementx
in a sorted array to maintain the array's sorted order. Here, it's used to find the minimum valid capacity.- The range from
left
toright
is provided along with a key functioncheck
whichbisect_left
uses to determine the validity of the capacity.True
represents the element to be inserted, corresponding to the condition of finding a workable capacity.
-
Return the Calculated Capacity:
- The minimum weight capacity is found when
bisect_left
concludes the search. It's computed asleft + position
whereposition
is the insertion point returned bybisect_left
. Sinceleft
is the starting point of the search range, adding the position gives us the exact weight capacity.
- The minimum weight capacity is found when
By leveraging binary search, the solution minimizes the number of times it needs to check for a viable shipping plan, which drastically reduces the time complexity compared to linearly searching through all possible capacities. The use of bisect_left
provides a concise and efficient way to perform the search. The check
function acts as a simulation/verification step that guarantees that the found capacity is indeed the lowest that can still ship all packages within the provided number of days.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have the following input where weights = [3, 2, 2, 4, 1]
represent the weights of the packages, and we need to ship all packages within days = 3
.
We first determine the search range for the ship's capacity:
- The heaviest package is
4
, so our lower boundleft
is4
. - The sum of all package weights is
3+2+2+4+1 = 12
, so our upper boundright
is13
(one more than the sum for binary search).
Now, we apply the binary search approach:
-
We start with the middle of our range. The initial guess for the ship's capacity will be
(left + right) / 2
which is(4 + 13) / 2 = 8.5
. We round this down to8
(since ship capacity must be an integer and binary search takes the lower mid). -
With a capacity of
8
, we simulate the loading using thecheck
function:- Day 1: We load
3 + 2 + 2
because adding the next package would exceed the capacity. - Day 2: We start with the next package and load
4
. - Day 3: The last package
1
is loaded.
We managed to load all the packages in
3
days which is within our alloweddays
. This indicates capacity8
is possible. - Day 1: We load
-
Since
8
worked, we now try to find if there is a smaller possible capacity. We adjust our search range toleft
remaining4
andright
becoming the current guess8
. -
Repeat the binary search process:
- New middle is
(4 + 8) / 2 = 6
. So we check capacity6
. - Day 1: We load
3 + 2
because adding another package would exceed the capacity. - Day 2: We continue with
2 + 4
, we reach the capacity exactly. - Day 3: We load the last package
1
.
Again, we have managed to load all the packages in
3
days, so capacity6
seems to work as well. - New middle is
-
We continue the binary search with the new range
left
is4
andright
is now6
. -
New middle is
(4 + 6) / 2 = 5
. So we check capacity5
.- Day 1: We load
3
and cannot add2
because it would exceed capacity, so we load just3
. - Day 2: We load
2 + 2
and stop there, as adding4
would exceed the capacity. - Day 3: We load
4
, but now we cannot load the last package as it would require an additional day.
In this case, we failed to load all packages within
3
days using capacity5
. This tells us the capacity of5
is too low. - Day 1: We load
-
Now adjust the range with
left
becoming6
, since5
didn't work, andright
staying6
.Given that
left
andright
are now the same, the search ends, and we have found that the minimum capacity needed is6
.
By using binary search and simulating the loading of packages, we determined that the minimum capacity of the ship to load all the packages within 3
days is 6
. This approach is efficient because instead of trying every capacity between the heaviest package and the total weight, we eliminate half of the possibilities with each step.
Solution Implementation
1from typing import List
2from bisect import bisect_left
3
4class Solution:
5 def shipWithinDays(self, weights: List[int], days: int) -> int:
6 # Helper function to check if the given capacity 'max_capacity' is enough
7 # to ship all the packages within 'days' days
8 def can_ship_with_capacity(max_capacity):
9 current_weight, day_count = 0, 1 # Initialize current total weight and day count
10 # Loop through the weights of the packages
11 for weight in weights:
12 current_weight += weight # Add package weight to current load
13 # If the current load exceeds the max capacity, start a new day
14 # and reset the current load to the current package's weight
15 if current_weight > max_capacity:
16 day_count += 1
17 current_weight = weight
18 # The capacity is enough if we can ship within required days
19 return day_count <= days
20
21 # Define the search space between largest single package and total weight
22 left, right = max(weights), sum(weights)
23
24 # Use binary search to find the minimum capacity needed to ship within 'days' days
25 # The search will find the first value where 'can_ship_with_capacity' returns True
26 min_capacity_needed = left + bisect_left(range(left, right), True, key=can_ship_with_capacity)
27
28 return min_capacity_needed
29
30# Example usage:
31# solution = Solution()
32# min_capacity = solution.shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)
33# print(min_capacity) # Output: 15
34
1class Solution {
2 public int shipWithinDays(int[] weights, int days) {
3 // Setting initial left boundary to the largest weight
4 // and right boundary to the sum of all weights
5 int leftBoundary = 0, rightBoundary = 0;
6 for (int weight : weights) {
7 leftBoundary = Math.max(leftBoundary, weight);
8 rightBoundary += weight;
9 }
10
11 // Binary search to find the minimum capacity of the ship that will work within given days
12 while (leftBoundary < rightBoundary) {
13 // Midpoint to test if it's a valid ship capacity
14 int midCapacity = (leftBoundary + rightBoundary) >> 1;
15 // Check if midCapacity is enough, if so, look for a smaller potential capacity
16 if (canShip(weights, midCapacity, days)) {
17 rightBoundary = midCapacity;
18 } else {
19 // Otherwise, discard midCapacity and look for a larger one
20 leftBoundary = midCapacity + 1;
21 }
22 }
23 // Return the minimum valid ship capacity
24 return leftBoundary;
25 }
26
27 // Helper method to determine if the given capacity can ship all weights within the given days
28 private boolean canShip(int[] weights, int capacity, int days) {
29 int currentLoad = 0; // Current weight load of the ship
30 int dayCount = 1; // Start with the first day
31
32 // Iterating over each weight to simulate the shipping process
33 for (int weight : weights) {
34 currentLoad += weight;
35 // If adding weight exceeds capacity, ship current load and increment day counter
36 if (currentLoad > capacity) {
37 currentLoad = weight; // Reset load with the current weight
38 dayCount++; // Move to the next day
39 }
40 }
41
42 // If the number of shipping days needed is within the allowed range, return true
43 return dayCount <= days;
44 }
45}
46
1#include <vector>
2#include <algorithm> // For max()
3using std::vector;
4using std::max;
5
6class Solution {
7public:
8 // Function to find the minimum capacity of a ship that can ship all the packages within 'days' days
9 int shipWithinDays(vector<int>& weights, int days) {
10 int minCapacity = 0; // Lower boundary of binary search - max weight in the shipment
11 int maxCapacity = 0; // Upper boundary of binary search - sum of all weights
12
13 // Calculate the minimum and maximum capacity
14 for (int weight : weights) {
15 minCapacity = max(minCapacity, weight);
16 maxCapacity += weight;
17 }
18
19 // Lambda function to check if mid value can work as the capacity
20 auto canShipWithCapacity = [&](int capacity) -> bool {
21 int currentWeightSum = 0; // Current weight sum of the ongoing shipment
22 int dayCount = 1; // Counter for the number of days needed
23
24 for (int weight : weights) {
25 currentWeightSum += weight;
26
27 // Check if adding the current weight exceeds capacity, if so, reset for the next day
28 if (currentWeightSum > capacity) {
29 currentWeightSum = weight;
30 dayCount++;
31 }
32 }
33
34 // Check if we can ship within the given number of days with the current capacity
35 return dayCount <= days;
36 };
37
38 // Binary search to find the minimum capacity required
39 while (minCapacity < maxCapacity) {
40 int midCapacity = (minCapacity + maxCapacity) / 2;
41
42 // Check if the midCapacity can be a possible solution, adjust search boundaries based on it
43 if (canShipWithCapacity(midCapacity)) {
44 maxCapacity = midCapacity;
45 } else {
46 minCapacity = midCapacity + 1;
47 }
48 }
49
50 // Return the minimum capacity needed to ship within 'days' days
51 return minCapacity;
52 }
53};
54
1function shipWithinDays(weights: number[], days: number): number {
2 // Initialize the lower and upper bounds for the binary search
3 let lowerBound = 0;
4 let upperBound = 0;
5
6 // Calculate the initial bounds for the capacity of the ship
7 for (const weight of weights) {
8 lowerBound = Math.max(lowerBound, weight); // The ship's capacity must be at least as much as the heaviest package
9 upperBound += weight; // The maximum capacity is the sum of all weights, i.e., shipping all at once
10 }
11
12 // Function to determine if it's possible to ship all packages within 'days' given a maximum capacity 'maxCapacity'
13 const canShipInDays = (maxCapacity: number): boolean => {
14 let currentWeightSum = 0; // Current total weight in the current shipment
15 let requiredDays = 1; // Start with 1 day, the minimum possible
16
17 for (const weight of weights) {
18 currentWeightSum += weight;
19
20 // If adding the current weight exceeds max capacity, need a new shipment (next day)
21 if (currentWeightSum > maxCapacity) {
22 currentWeightSum = weight; // Reset the currentWeightSum with the current weight as the start for the next day
23 ++requiredDays; // Increment the day counter as we move to the next day
24 }
25 }
26
27 // Return true if the number of required days is less than or equal to the given days, false otherwise
28 return requiredDays <= days;
29 };
30
31 // Perform a binary search to find the minimum capacity needed to ship within 'days'
32 while (lowerBound < upperBound) {
33 const midCapacity = Math.floor((lowerBound + upperBound) / 2); // Mid-point of the current bounds
34
35 // If it's possible to ship with this capacity, reduce the upper bound to midCapacity
36 if (canShipInDays(midCapacity)) {
37 upperBound = midCapacity;
38 } else {
39 // Otherwise, increase the lower bound just above midCapacity
40 lowerBound = midCapacity + 1;
41 }
42 }
43
44 // The lower bound at the end of the binary search will be the minimum capacity needed to meet the requirement
45 return lowerBound;
46}
47
Time and Space Complexity
The time complexity of the code is O(n * log(S))
, where n
is the number of elements in weights
, and S
is the sum of weights minus the maximum weight in weights
. This is because the binary search is performed over a range with left
and right
as lower and upper bounds, respectively. The check
function, called at each step of the binary search, runs in O(n)
time since it iterates through all the elements of weights
. Since the binary search narrows the range by half each time, it will run log(S - max(weights))
times.
The space complexity of the code is O(1)
as it uses a constant amount of space. The check
function uses variables to store the current weight sum and the count of days, both of which do not depend on the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!