Aggressive Cows, thesarfo

Given stall positions and a number of cows, place all cows in stalls to maximize the minimum distance between any two cows. (Problem link)

Search space: [1, max(stalls) - min(stalls)] after sorting the stalls. Larger candidate distances are harder to satisfy, so feasibility flips from “yes” to “no” at some threshold — maximize over the “yes” side.

public class AggressiveCows {
    static int maximizeMinDistance(int[] stalls, int cows) {
        Arrays.sort(stalls);

        int low = 1;
        int high = stalls[stalls.length - 1] - stalls[0];
        int result = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (canPlaceCows(stalls, cows, mid)) {
                result = mid;
                low = mid + 1; // try for a larger distance
            } else {
                high = mid - 1; // try for a smaller distance
            }
        }

        return result;
    }

    static boolean canPlaceCows(int[] stalls, int cows, int distance) {
        int count = 1;
        int lastPosition = stalls[0];

        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPosition >= distance) {
                count++;
                lastPosition = stalls[i];
                if (count == cows) {
                    return true;
                }
            }
        }

        return false;
    }
}

Time: O(n log n) for sorting + O(n log(maxDistance)) for the search.