Find close pairs of real points in a set Given an array $S$ with $n$ real numbers. Design a linear time algorithm that finds $x,y \in S$ such that that $|x-y| \leq \frac{max(S)-min(S)}{n-1}$.
I was thinking that it is similar to the closest point problem but that can only be solved in O(nlogn).
Please help
Hint: by the pigeon principle, if $n$ pigeons have to go into $n- 1$ holes, at least one hole has two pigeons in it. Now let your pigeons be numbers, and make sure that if two numbers go in the same hole, they solve your problem.