Baseline Binary Search · In Search Space O(n log S), where S is the total weight · O(1)
A dock must push a queue of pallets onto ships within a fixed number of sailings. Pallets load strictly in queue order, a sailing's manifest cannot exceed the ship's rated capacity, and underruns waste deck space. Find the smallest rating that clears the queue in the allowed number of sailings.
Input: An array weights of n positive integers, loaded strictly in order, and an integer days.
Output: The least ship capacity that lets every pallet ship within days sailings.
1 <= weights.length <= 5 * 10^41 <= weights[i] <= 5001 <= days <= weights.lengthInput: {"weights":[1,2,3,4,5,6,7,8,9,10],"days":5}
Output: 15
Loads of 15, 13, 8, 9 and 10 across five sailings clear the queue, and no smaller rating manages it.
Input: {"weights":[3,2,2,4,1,4],"days":3}
Output: 6
A rating of 6 partitions the queue into 3+2, 2+4 and 1+4; a rating of 5 would force a fourth sailing.