Aggressive Cows
Place k cows in stalls (positions on a line) maximizing the minimum distance between any two cows.
02
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.
03
Approach
1
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.
2
Binary search on distance
Search d in [1, span]. Feasible → try bigger (lo = mid+1, remember mid); infeasible → smaller.
3
Max-min duality
Maximize-the-minimum → search the answer and test with ≥; minimize-the-maximum (pages) tests with ≤. Same skeleton.
04
Solution & live demo
python
▶1def aggressive_cows(stalls, k):
▶2 stalls.sort()
▶3 def can_place(d):
▶4 count, last = 1, stalls[0]
▶5 for s in stalls[1:]:
▶6 if s - last >= d:
▶7 count += 1; last = s
▶8 return count >= k
▶9 lo, hi, best = 1, stalls[-1] - stalls[0], 0
▶10 while lo <= hi:
▶11 mid = (lo + hi) // 2
▶12 if can_place(mid): best = mid; lo = mid + 1
▶13 else: hi = mid - 1
▶14 return best
05
Edge cases
k = 2
Answer is simply the span — first and last stall — and the search finds it.
Stalls unsorted on input
Sort first; greedy placement depends on order.
06
Complexity
Time
O(n log D)
Space
O(1)
D = span of stall positions.