Loading problem...
You are tasked with scheduling cargo shipments from a warehouse to a destination port. A series of packages are arranged on a loading dock, and they must be loaded onto transport vessels in their exact sequential order without rearrangement.
Each package has a specific weight given by the array weights, where weights[i] represents the weight of the i-th package in the loading sequence. You have exactly days days to complete all shipments, and each day you can dispatch one vessel loaded with consecutive packages from the remaining queue.
The vessel you use each day has a weight capacity limit. If the total weight of loaded packages exceeds this capacity, the shipment cannot proceed. Your objective is to determine the minimum vessel capacity required such that all packages can be successfully shipped within the given deadline.
Key Rules:
days days.Return the smallest possible vessel capacity that allows all packages to be shipped on time.
weights = [1,2,3,4,5,6,7,8,9,10]
days = 515A vessel capacity of 15 is the minimum required to ship all packages within 5 days. The optimal schedule is: • Day 1: Packages with weights 1, 2, 3, 4, 5 (total = 15) • Day 2: Packages with weights 6, 7 (total = 13) • Day 3: Package with weight 8 (total = 8) • Day 4: Package with weight 9 (total = 9) • Day 5: Package with weight 10 (total = 10)
Note that packages must be loaded sequentially, so a capacity of 14 would fail because you cannot reorder packages to optimize loading.
weights = [3,2,2,4,1,4]
days = 36With capacity 6, the shipments can be scheduled as: • Day 1: Packages with weights 3, 2 (total = 5) • Day 2: Packages with weights 2, 4 (total = 6, exactly at capacity) • Day 3: Packages with weights 1, 4 (total = 5)
weights = [1,2,3,1,1]
days = 43With capacity 3: • Day 1: Package with weight 1 (total = 1) • Day 2: Package with weight 2 (total = 2) • Day 3: Package with weight 3 (total = 3, exactly at capacity) • Day 4: Packages with weights 1, 1 (total = 2)
Constraints