Pattern visualizer
Aggressive Cows
Nothing in the stall list is the answer, so there is no cell to search for. Turn it around and ask a yes/no question instead: can the cows be seated with every pair at least d apart? A left-to-right greedy answers that in one pass, and the answers are monotonic — if d works, every smaller gap works, and once d fails every larger gap fails too. That yes/no flip is exactly the sorted-true-then-false shape binary search needs, so we search d itself and keep the largest d that still answers yes. Animated on: stalls = 29, 1, 41, 20, 58, 12, 70, 5 and k = 4 cows — seat one cow per stall so that the smallest distance between any two cows is as large as possible..
Binary search the ANSWER, then greedily test it
8 stalls at 29, 1, 41, 20, 58, 12, 70, 5 and 4 cows to seat. The cows fight, so we want the placement where the CLOSEST pair of cows is as far apart as possible.
1FUNCTION maxMinDistance(stalls, k):2 stalls <- SORT(stalls)3 low <- 14 high <- stalls[LENGTH(stalls) - 1] - stalls[0]5 WHILE low <= high6 mid <- (low + high) / 27 IF canPlace(stalls, k, mid)8 best <- mid9 low <- mid + 110 ELSE11 high <- mid - 112 RETURN best
← / → step · space play · Home restart