Pattern visualizer
Capacity to Ship Packages
Nothing here is sorted, so there is no array to binary search. What IS sorted is the capacity line: if a 7-ton ship can finish in time then an 8-ton ship certainly can, and if a 5-ton ship cannot then neither can a 4-ton one. Feasibility flips from no to yes exactly once along that line, and binary search hunts that flip. Each guess is tested by loading the ship greedily — keep adding packages until the next one would overflow, then start a new day — which is optimal because delaying a package you could carry today can never save a day later. Animated on: weights = [3,2,2,4,1,4], days = 3 — packages must ship in the given order; find the smallest daily ship capacity that clears them all within 3 days..
Binary search the capacity, greedy-pack to test it
6 packages must go out in this exact order within 3 days. A ship smaller than 4 could never carry the heaviest package, and 16 carries everything in one day, so the answer is somewhere in [4, 16] — and raising the capacity never needs MORE days, which is the monotonicity binary search runs on.
1FUNCTION shipWithinDays(weights, days):2 low <- MAX(weights)3 high <- SUM(weights)4 WHILE low < high:5 mid <- (low + high) / 26 IF DAYS_NEEDED(weights, mid) <= days:7 high <- mid8 ELSE:9 low <- mid + 110 RETURN low
← / → step · space play · Home restart