Capacity To Ship Packages Within D Days

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.

The idea is to use binary search instead of linear search. The reason being Binary search can be applied on a sorted range, and in this case, from 'minShipCapacity' to 'maxShipCapacity', it is also sorted range. So, if we can use binary search, then we can cut down the time complexity from O(sum) to O(log(sum)) for searching, which increases the efficiency.

From the previous approach, we already found out the range in which the least weight capacity can lie. Then use a while loop to find the answer.

• Initialize 'minShipCapacity' = maximum value of the array 'weights' and 'maxShipCapacity' = sum of all the array 'weights' values.
• Execute a while loop with the condition that 'maxShipCapacity' >= 'minShipCapacity':

1. Initialize capacity = ('minShipCapacity' + 'maxShipCapacity')/2;
2. 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?
   1. 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.
   2. 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.
   3. Iterate over the array 'weights':
      1. Check if, after adding the current element, the total weight for the current day exceeds the weight capacity of the ship or not.
      2. If it doesn’t exceed, then add the current weight to currentDayWeight.
      3. 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.
   4. 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.
   5. Return true as the packages can be delivered within ‘d’ days.

• If it’s valid, then change the value of 'maxShipCapacity' to capacity - 1.
• If not, then change the value of 'minShipCapacity' to capacity + 1.
• Return ‘'minShipCapacity'’ as the final answer. The idea behind this step is that we are storing the minimum of all the possible values of the least weight capacity, i.e., whenever we encounter any possible value which is less than the current value of l, then we update it.