Binary search on the answer — Aggressive Cows, Book Allocation, Painter’s Partition, EKO, ROTI-Prata

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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 driver
function 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.