A farmer has a long barn containing N stalls.
Each stall is placed on a straight line, and the position of every stall is represented by an integer coordinate.
The farmer needs to place C cows into these stalls.
Since the cows become aggressive when they are too close to one another, the farmer wants to place them in such a way that the closest pair of cows is as far apart as possible.
Your task is to return the maximum possible value of the minimum distance between any two placed cows.
Method Signature
int largestMinimumDistance(List<Integer> stallPositions, int cowCount)
Parameters
stallPositions: A list of integers where each value represents the position of one stall.cowCount: The number of cows that must be placed into distinct stalls.
Return Value
- Return one integer: the largest possible minimum distance between any two placed cows.
Constraints
2 ≤ stallPositions.size() ≤ 100,0002 ≤ cowCount ≤ stallPositions.size()0 ≤ stallPositions.get(i) ≤ 1,000,000,000- Each cow must be placed in exactly one stall.
- No two cows can be placed in the same stall.
- The stall positions may be provided in any order.
- The same stall position will not appear more than once.
Examples
Example 1
Method Call:
largestMinimumDistance(stallPositions = List.of(1, 3, 7, 12, 20), cowCount = 3)
Output:
8
Explanation:
One optimal placement is at positions 1, 12, and 20.
The distances between adjacent placed cows are 11 and 8, so the minimum distance is 8.
It is not possible to place 3 cows with a minimum distance greater than 8.
Example 2
Method Call:
largestMinimumDistance(stallPositions = List.of(5, 11, 30, 1), cowCount = 2)
Output:
29
Explanation:
Since only 2 cows need to be placed, the best strategy is to place them in the two farthest stalls.
The farthest positions are 1 and 30, giving a distance of 29.
Example 3
Method Call:
largestMinimumDistance(stallPositions = List.of(10, 20, 5, 30), cowCount = 4)
Output:
5
Explanation:
All 4 cows must be placed because there are exactly 4 cows and 4 stalls.
After sorting, the stall positions are 5, 10, 20, and 30.
The adjacent distances are 5, 10, and 10, so the minimum distance is 5.
Example 4
Method Call:
largestMinimumDistance(stallPositions = List.of(0, 4, 7, 10, 14, 20), cowCount = 4)
Output:
6
Explanation:
One optimal placement is at positions 0, 7, 14, and 20.
The adjacent distances are 7, 7, and 6, so the minimum distance is 6.
A minimum distance of 7 is not possible for placing 4 cows.