Implement the aggressiveCowsDistance method that maximizes the minimum distance between placed cows.
The input contains stall positions stalls, its length size, and the number of cows. Your task is to place all cows in the stalls so that the minimum distance between any two cows is as large as possible.
Only one cow can be placed in a stall. The answer is the largest distance value that can still allow all cows to be placed.
For example, with stalls [1,2,4,8,9] and 3 cows, the best minimum distance is 3.
Example 1
[1,2,4,8,9]533Example 2
[1,2,8,4,9]533Example 3
[1,2,3,4,5]524Sort the stall positions first because placement depends on distance order.
Then use binary search on the possible minimum distance. For a guessed distance, greedily place the first cow in the first stall, then place each next cow in the earliest stall that is at least that distance away from the last placed cow.
If all cows can be placed, the distance is possible, so try a larger distance. Otherwise, try a smaller distance.
Pseudocode:
function canPlaceCows(stalls, size, cows, distance):
count = 1
lastPosition = stalls[0]
for i from 1 to size - 1:
if stalls[i] - lastPosition >= distance:
count++
lastPosition = stalls[i]
return count >= cows
function aggressiveCowsDistance(stalls, size, cows):
sort stalls
left = 1
right = stalls[size - 1] - stalls[0]
answer = 0
while left <= right:
mid = left + (right - left) / 2
if canPlaceCows(stalls, size, cows, mid):
answer = mid
left = mid + 1
else:
right = mid - 1
return answer