Smallest Interval

Limits: 1s, 512 MB

Alice has a collection of N numbers. She would like to place them on a number line. She places each of the N numbers on the point corresponding to its value on the number line. Now she wonders, what’s the size of the smallest interval on the number line such that there are at least K numbers from her collection on that interval?

This is a companion discussion topic for the original entry at