The hives kept apart

Problem

Nicasio cleared several patches along the hill path, but he could only afford hives hives. The bees of two neighboring hives rob each other if they end up close together, so he wants to place them so that the closest pair in the whole apiary ends up as far apart as it can: if one arrangement leaves two hives 3 steps apart and another leaves them 4, the good one is the one with 4.

Each hive goes in one clearing and only one fits in each clearing. The distance between two hives is the difference of the steps where their clearings are. What a given arrangement is measured by is its smallest spacing, the one of the closest pair, and that is the one that has to be made big. A smaller spacing is never harder to get: the arrangement that leaves every hive 4 steps apart or more leaves them 3 or more too.

Write a function that takes spots, a list of distinct whole numbers of 0 or more with the step of each clearing (at least two, in any order), and hives, a whole number from 2 to the number of clearings. Return a whole number: the smallest spacing of the best arrangement.

With clearings at steps 1, 2, 8, 4 and 9 and three hives, the answer is 3: they go in the 1, the 4 and the 9, and the spacings are 3 and 5, so the smallest one is 3. Sharing them out by eye is no use: from the 1 to the 9 there are 8 steps and the easy sum says 4, but that would need clearings at the 1, the 5 and the 9, and there is no clearing at the 5.

If Nicasio has one hive per clearing there is nothing to choose: they all go in and the answer is the spacing of the two closest clearings.

There are paths with up to 60 clearings and the steps reach a billion.

Examples

• The example

  [1, 2, 8, 4, 9], 3 → 3

• Six clearings of two digits

  [0, 3, 4, 7, 10, 9], 4 → 3

• Just two hives

  [1, 5], 2 → 4

• One hive in every clearing

  [2, 5, 6, 13], 4 → 1

• Evenly spaced clearings

  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3 → 4

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def spacing(spots, hives):
    pass

function spacing(spots, hives) {
}