Aggresive cows

Baseline Binary Search · In Search Space O(n log n) (sorting) plus O(n log D) for the search over distances · O(1)

Spreading Calibration Probes Along a Rail

A QA rig places m sensor probes on slots fixed along a straight rail so that the two closest probes end up as far apart as possible - closer spacing causes interference. Slots are given in arbitrary order. Choose the placement that maximizes that minimum spacing and report the spacing achieved.

Input: An array position of n slot coordinates and an integer m, the number of probes to place.

Output: The largest possible value of the minimum distance between any two probes.

Constraints

2 <= n <= 10^5
2 <= m <= n
0 <= position[i] <= 10^9

Examples

Example 1

Input: {"position":[1,2,3,4,7],"m":3}
Output: 3
Probes at slots 1, 4 and 7 space every pair at least 3 apart, and no placement beats that.

Example 2

Input: {"position":[1,2,4,8,9],"m":3}
Output: 3
Placing at 1, 4 and 8 keeps the tightest pair 3 apart; demanding 4 strands the third probe.

Solve this in your browser →

Also on LeetCode ↗