Spread Out the Sensors

A long pipeline has mounting points at the distances (in metres from the pump) listed in points. You must fit k leak sensors, each on a different mounting point. Sensors placed close together give overlapping readings, so you want the two closest sensors to be as far apart as possible.

Write widest_gap(points, k) that returns the largest possible distance between the two closest sensors.

Examples

widest_gap([2, 5, 9, 11, 16, 20], 3)   # returns 9
widest_gap([10, 3, 7, 1], 2)           # returns 9
widest_gap([0, 5, 6, 10, 15], 4)       # returns 5

In the first example sensors at 2, 11 and 20 are 9 metres apart from each other. In the second example the two sensors go at the two ends, 1 and 10.

Constraints

• 2 <= k <= len(points) <= 100,000
• 0 <= points[i] <= 10^9
• The points are all different, but not sorted