SPOJ.com - Problem AGGRCOW | Problems

Given N stalls and C cows, place cows such that the minimum distance between any two cows is maximized.

Example: stalls = [1, 2, 4, 8, 9], C = 3 → Output: 3

Sample Input

—

Sample Output

—

Constraints

2 <= N <= 10^5
0 <= positions[i] <= 10^9
2 <= C <= N

Topics

Sorting&Searching

Binary Search on Answer

function aggressiveCows(stalls, c) {
  stalls.sort((a,b)=>a-b);
  let lo = 1, hi = stalls[stalls.length-1] - stalls[0];
  while (lo <= hi) {
    const mid = (lo+hi)>>1;
    let cows = 1, last = stalls[0];
    for (let i = 1; i < stalls.length; i++) {
      if (stalls[i] - last >= mid) { cows++; last = stalls[i]; }
    }
    if (cows >= c) lo = mid + 1; else hi = mid - 1;
  }
  return hi;
}

Time: O(n log(max_dist)) | Space: O(1)

Saved in this browser only. Private to you.