SPOJ.com - Problem AGGRCOW Hard 0 attempts

SPOJ.com - Problem AGGRCOW

Hard Sorting&Searching Other

There are N stalls positioned along a line and C cows that need to be placed into them, at most one cow per stall. Choose stall positions for every cow so that the smallest gap between any two occupied stalls is as large as possible, and return that maximized minimum distance.

Input Format
Implement aggressiveCows(stalls, c). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
stalls = [1,2,4,8,9]
c = 3
Output
3

Example 2

Input
stalls = [1,2]
c = 2
Output
1
Constraints
  • 2 <= N <= 10^5
  • 0 <= positions[i] <= 10^9
  • 2 <= C <= N
Test Cases (2)
Case 1
Args: [[1,2,4,8,9],3] Expected: 3
Case 2
Args: [[1,2],2] Expected: 1
Topics
Sorting&Searching

Binary Search on Answer

javascript
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 = Math.floor(lo + (hi-lo)/2);
    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.

JavaScript