Binary Search on the Answer
Cast feasibility problems as binary search over a monotone predicate. Drills cover min capacity, max chunk, and the standard template.
1,159 views
33
You must ship weights over D days. Capacity cap is feasible if the ships can finish in D days. Write feasible(cap).
Examples
Example 1:
Input: weights = [1, 2, 3, 4, 5], D = 3, cap = 6
Output: True
Explanation: Greedy pack: [1, 2, 3] (sum 6), [4] (sum 4), [5] (sum 5). 3 ships, fits in D = 3 days.Example 2:
Input: weights = [1, 2, 3, 4, 5], D = 3, cap = 5
Output: False
Explanation: Greedy fills [1, 2] then [3] then [4] then [5] which is 4 ships, exceeding D = 3.def feasible(weights, D, cap):
# TODO: return True if `cap` ship capacity finishes all weights in <= D days
passWhat makes a problem suitable for binary search on the answer? Name the property and explain why it matters.
Build the wrapper that returns the minimum feasible cap using a feasibility predicate that greedily packs ships and returns whether the count is at most D, and a half-open binary search.
Examples
Example 1:
Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], D = 5
Output: 15
Explanation: Search [max(weights), sum(weights)] = [10, 55]. The smallest cap that finishes the shipment in 5 days is 15 (packs are [1..5], [6, 7], [8], [9], [10] or similar). The leftmost-true template returns 15.def ship_within_days(weights, D):
# TODO
passFor a 'maximize the minimum' problem (e.g. place m boxes in n shelves to maximize the smallest gap), do you binary-search for the largest true or the smallest true, and what direction does the loop move?
What is the time complexity of binary search on the answer in terms of the answer range [lo, hi] and a per-feasibility cost T?