Capacity To Ship Packages Within D Days

Share

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Example 1
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: 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
Explanation: 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 2
Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1
Constraints:

Contents

Solution 1 - Using binary search

As per the problem statement, we were given some weights and we were told how many days we can utilize to ship those weights. We have to find the 'least capacity ship' required inorder to deliver those weights.
Remember one thing, If you pick a higher capa

In this approach, we will apply Binary Search algorithm, since the input array is sorted in ascending order, we will use two pointers left and right to point to left and right end of array, and then using a while loop, compute the middle index mid = left + right _____________ 2 , then check if the element at mid index, based on the element found at mid index, we can draw three conclusions.

  • If the element at mid index is the target, then return the mid index, since the element is same, it can be inserted at this position.
  • If the element at mid index is greater than target, since the array is sorted in ascending order, this means that the target lies on left half of the array, so we will update right index to mid-1.
  • If the element at mid index is less than target, since the array is sorted in ascending order, this means that the target lies on right half of the array, so we will update left index to mid+1.

If that target is not found, we will return left index as answer, this is where the target element can be inserted.

Java
Complexity Analysis:

Time complexity: Above code runs in O(log n) time where n is the length of input array nums.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code