Capacity to Ship Packages within D Days
Binary Search on Answers DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Find the least weight capacity of a ship to ship all packages within d days, given an array of package weights and constraints on shipping order and daily limit., Arrays, Binary Search, Brute Force, Functions, Loops, Conditional Statements, Time Complexity, Space Complexity, Big O Notation, binary search, search space optimization, complexity analysis, greedy algorithm, Greedy Approach.
Ship Within D Days 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. Input Specification: The input consists of an array of integers weights representing the weights of packages and an integer d representing the maximum number of days allowed for shipment. Output Specification: Return a single integer, the least weight capacity required. Constraints: The capacity must be greater than or equal to the maximum weight of any single package. The capacity must be less than or equal to the sum of all package weights. Sample Test Cases: Example 1: Input: weights = [5, 4, 5, 2, 3, 4, 5, 6], d = 5 Output: 9 Explanation: If the ship capacity is 9, the shipment will be done in the following manner: Day 1: 5, 4 (Total: 9) Day 2: 5, 2 (Total: 7) Day 3: 3, 4 (Total: 7) Day 4: 5 (Total: 5) Day 5: 6 (Total: 6) So, the least capacity should be 9. Example 2: Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], d = 1 Output: 55 Explanation: To ship all the goods in a single day, the weight capacity should be the summation of all the weights, which is 55.