Binary search on the answer — Aggressive Cows, Book Allocation, Painter’s Partition, EKO, ROTI-Prata
Problem
A family of problems where you binary-search the answer itself:
Aggressive Cows — place c cows in n stalls (given positions) so that the minimum distance between any two cows is as large as possible. Return that distance.
Book Allocation / Painter's Partition — split an array into k contiguous parts so that the largest part-sum is as small as possible. Return that sum.
EKO — choose the tallest saw height H such that the wood cut from the tree tops above H is at least M.
ROTI-Prata — cooks with given ranks make p pratas together (a rank-r cook needs r, 2r, 3r… minutes for successive pratas). Return the minimum time.
Example 1
Input: Cows: stalls = [1, 2, 4, 8, 9], cows = 3 Output: 3
Place them at 1, 4 and 8 (or 9).
Example 2
Input: Books: pages = [12, 34, 67, 90], students = 2 Output: 113
[12, 34, 67] and [90].
Also asked as: Aggressive cows · Book Allocation Problem · Painters Partition Problem · EKOSPOJ · ROTI-Prata SPOJ · Job Scheduling Algo
Test cases
Case 1
Input: [1,2,4,8,9], 3 Expected: 3
Case 2
Input: [10,1,2,7,5], 3 Expected: 4
Case 3
Input: [1,2], 2 Expected: 1
View solutionHide solution3 approaches
1. The pattern
Time O(n · log(range))Space O(1)
These all ask for the min/max feasible value of some quantity. The feasibility check is monotonic, so binary-search the answer space and test each candidate greedily in O(n).
// generic driverfunction binarySearchAnswer(lo, hi, feasible) { // finds the smallest value in [lo, hi] for which feasible() is true while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); feasible(mid) ? (hi = mid) : (lo = mid + 1); } return lo;}2. Aggressive Cows — maximise the minimum gap
Time O(n log n + n log(range))Space O(1)
Sort stalls. For a candidate min distance d, greedily place cows; feasible if you can place all C. Search for the largest feasible d.
function aggressiveCows(stalls, cows) { stalls.sort((a, b) => a - b); const canPlace = (d) => { let placed = 1, last = stalls[0]; for (let i = 1; i < stalls.length; i++) if (stalls[i] - last >= d) { placed++; last = stalls[i]; } return placed >= cows; }; let lo = 1, hi = stalls[stalls.length - 1] - stalls[0], ans = 0; while (lo <= hi) { const mid = (lo + hi) >> 1; if (canPlace(mid)) { ans = mid; lo = mid + 1; } else hi = mid - 1; } return ans;}3. Book Allocation / Painter’s Partition — minimise the maximum load
Time O(n log(sum))Space O(1)
For a candidate max load per student/painter, greedily fill; feasible if the number of groups ≤ k. Search for the smallest feasible max.
function allocateBooks(pages, students) { const fits = (limit) => { let groups = 1, cur = 0; for (const p of pages) { if (p > limit) return false; if (cur + p > limit) { groups++; cur = p; } else cur += p; } return groups <= students; }; let lo = Math.max(...pages), hi = pages.reduce((a, b) => a + b, 0), ans = hi; while (lo <= hi) { const mid = (lo + hi) >> 1; if (fits(mid)) { ans = mid; hi = mid - 1; } else lo = mid + 1; } return ans;}EKO (cut trees at height h so total wood ≥ M): binary-search h, feasibility = Σ max(0, tree − h) ≥ M. ROTI-Prata (finish P pratas in time T with cooks of rank r): binary-search T, feasibility = Σ (pratas each cook can make in T) ≥ P.