The Perfect Picnic Spot
UptoSkills Arena is organizing a grand picnic! As the chief organizer, you are tasked with selecting the best spots for food stalls. You are given the locations of n potential picnic spots along a straight line, represented by their coordinates x_1, x_2, ..., x_n. You need to choose exactly k of these spots to set up the food stalls. To ensure everyone has easy access, you want to maximize the minimum distance between any two chosen stall locations. Find the largest possible value d such that you can select k spots where the distance between any pair of selected spots is at least d.
Input
The first line contains two integers n and k (2 <= k <= n <= 200000). The second line contains n space-separated integers x_1, x_2, ..., x_n (0 <= x_i <= 10^9).
Output
Print a single integer: the maximum possible minimum distance d.
Constraints
2 <= k <= n <= 200000
0 <= x_i <= 10^9
n is the number of potential spots.
k is the number of spots to choose.
x_i are the coordinates of the spots, not necessarily sorted.
Example 1
5 3 1 2 4 8 9
3
Sort: [1, 2, 4, 8, 9]. Choose spots 1, 4, 8 or 1, 4, 9. Max min dist is 3.
Example 2
6 4 0 10 20 30 40 50
10
Sort: [0, 10, 20, 30, 40, 50]. Choose 0, 10, 20, 30 (min dist 10) or 0, 10, 20, 40 (min dist 10) or 0, 10, 20, 50 (min dist 10) etc. Best is 0, 10, 20, 30, 40, 50. Choose 0, 10, 20, 30. Max min dist is 10.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 1 2 4 8 9
6 4 0 10 20 30 40 50