Capacity To Ship Packages Within D Days

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
156 upvotes
Asked in companies
Morgan StanleyAmazonCoinbase

Problem statement

You are the owner of a Shipment company. You use conveyor belts to ship packages from one port to another. The packages must be shipped within 'd' days.


The weights of the packages are given in an array 'weights'. The packages are loaded on the conveyor belts every day in the same order as they appear in the array. The loaded weights must not exceed the maximum weight capacity of the ship.


Find out the least-weight capacity so that you can ship all the packages within 'd' days.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains two integers, ‘n’ and ‘d’, denoting the size of the array ‘weights’ and the maximum weight capacity of the ship.

The second line contains ‘n’ integers denoting the elements of the array ‘weights’.
Output Format: 
Return the least weight capacity so that you can ship all the packages within 'd' days.
Note: 
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Sample Input 1:
8 5
5 4 5 2 3 4 5 6
Sample Output 1:
9
Explanation for Sample Input 1:
In the test case, the given weights are [5,4,5,2,3,4,5,6] and these are needed to be shipped in 5 days. We can divide these weights in the following manner:
Day         Weights            Total
1        -   5, 4          -    9
2        -   5, 2          -    7
3        -   3, 4          -    7
4        -   5             -    5
5        -   6             -    6
The least weight capacity needed is 9, which is the total amount of weight that needs to be taken on Day 1.
Sample Input 2:
10 1
1 2 3 4 5 6 7 8 9 10
Sample Output 2:
55
Constraints:
1 <= n <= 10^5
1 <= d <= 10^5
1 <= weights[i] <= 500

Time Limit: 1 sec
Hint

Iterate through every possible value of weight that the ship can have. 

Approaches (2)
Bruteforce

The idea is to find the range in which the weight capacity of the ship can lie and then iterate in the given range and find the smallest weight capacity such that we can ship all the packages within ‘d’ days. The minimum value of the ship capacity is the maximum weight in the given array 'weights', and the maximum value of the ship capacity is the sum of all the weights of the array 'weights'.

 

The steps are as follows:

  • Initialize 'minShipCapacity' = maximum value of the array 'weights' and 'maxShipCapacity' = sum of all the values of array 'weights'.
  • Iterate from i = 'minShipCapacity' to 'maxShipCapacity':
  • Check if the given value of i is taken as the least weight capacity then Will it be possible to ship all the packages within d days?
    • Define a function 'checkValidity', which takes three arguments ‘capacity’, 'weights', and ‘d’, which denotes the current weight capacity for which we are checking, the given array 'weights', and the given integer ‘d’, respectively.
    • Initialize two variables, ‘currentDay’ equal to 1 and  'currentDayWeight' to 0, which denotes the number of the day for which we are shipping the packages, and the total weight that can be carried on the Kth Day, respectively.
    • Iterate over the array 'weights':
      • Check if, after adding the current element, the total weight for the current day exceeds the weight capacity of the ship or not.
      • If it doesn’t exceed, then add the current weight to currentDayWeight.
      • If it exceeds, then increase the required number of days by incrementing the ‘currentDay’ and then set the value of 'currentDayWeight' to the current element.
  • Check if ‘currentDay’ becomes greater than ‘d’. If it becomes greater than ‘d’, it means packages can’t be delivered in the expected number of days. Return false.
  • Return true as the packages can be delivered within ‘d’ days.
  • If 'checkValidity' returns true, then return i as it is the least answer.
Time Complexity

O(sum * n), where 'sum' denotes the sum of weights of all packages and ‘n’ is the number of packages.

 

We are iterating from the maximum value of the array ‘weights’ to the sum of all values of ‘weights’ In each iteration, we are iterating over the array weights. 

 

Hence the overall time complexity is O(sum * n).

Space Complexity

O(1), as we are using constant space.

Code Solution
(100% EXP penalty)
Capacity To Ship Packages Within D Days
Full screen
Console