Aggressive Cows
Place k cows in stalls (positions on a line) maximizing the minimum distance between any two cows.
Intuition
Mirror image of Allocate Pages: 'can cows be placed with every gap ≥ d?' is a greedy sweep, and shrinking d only makes it easier — monotone again. Binary search the largest feasible d.
The giveaway is "maximise the minimum" (or "minimise the maximum"). You can't compute that directly, but you can check a guess: given a distance d, greedily place cows and see if k fit. That check is monotone — if d works, every smaller d works too — so binary search the answer. Allocate-minimum-pages, split-array-largest-sum and koko-eating-bananas are all this same template.
Approach
Feasibility by greedy placement
Sort stalls; place the first cow in stall 0, then each next cow in the first stall ≥ d beyond the previous. Count placed cows.
Binary search on distance
Search d in [1, span]. Feasible → try bigger (lo = mid+1, remember mid); infeasible → smaller.
Max-min duality
Maximize-the-minimum → search the answer and test with ≥; minimize-the-maximum (pages) tests with ≤. Same skeleton.
Solution & live demo
Common pitfalls
Forgetting to sort the stalls
def can_place(d):
count, last = 1, stalls[0]stalls.sort()
def can_place(d):
count, last = 1, stalls[0]The greedy placement assumes each stall is further right than the last, so s - last measures a real gap. On unsorted input that difference can be negative and the count is meaningless.
Searching over stall indices instead of distances
lo, hi = 0, len(stalls) - 1
lo, hi = 1, stalls[-1] - stalls[0]
The thing being searched is the answer — a distance — not a position in the array. The range runs from 1 to the widest possible separation; binary searching indices answers a different question entirely.
Moving the bound the wrong way on success
if can_place(mid): hi = mid - 1 else: lo = mid + 1
if can_place(mid): best = mid; lo = mid + 1 else: hi = mid - 1
A feasible distance is a candidate you want to beat, since bigger is better here. Shrinking hi on success searches downward and returns the smallest workable distance rather than the largest.
Edge cases
Answer is simply the span — first and last stall — and the search finds it.
Sort first; greedy placement depends on order.