Chess Tournament (Largest Minimum Distance)

Binary SearchGreedySorting

Set 1 • 90 min

Problem Statement

In a Goldman Sachs sponsored chess tournament, there are n rooms situated along a straight line at positions positions[0], ..., positions[n-1].

You need to assign c players to rooms such that the minimum distance between any two players is as large as possible to prevent noise distraction.

Return that largest minimum distance.

Candidate Instructions

▸Sort room positions.
▸Binary search the answer over range [1, max(pos) - min(pos)].
▸Use a greedy check: place the first player at pos[0], and subsequent players at the earliest room with distance >= d.

Input Format

▸First line: two integers n and c.
▸Second line: n space-separated integers representing room positions.

Output Format

▸Print the largest minimum distance.

Constraints

2 <= n <= 10^5
2 <= c <= n
0 <= positions[i] <= 10^9

Edge Cases

▸c == 2 (distance is max(positions) - min(positions))
▸c == n (distance is min adjacent difference)

Sample Test Cases

Example 1

Input

5 3
1 2 4 8 9

Output

Explanation

Assign 3 players to positions 1, 4, and 8 (or 9).

Distances between adjacent players: |4 - 1| = 3, |8 - 4| = 4. Minimum distance = 3.

No assignment can achieve minimum distance > 3.

Complexity

TimeO(N log(max_pos - min_pos))

SpaceO(1)

Expected Approach

Binary search the distance d. Sort the positions. A greedy validator canPlace(d) places the first player at position 0, then places each subsequent player at the first position >= lastPlaced + d. If placedCount >= c, search higher half.

Chess Tournament (Largest Minimum Distance)

Solution & Code