Split into groups that stay apart
Stop the cheapest-first process early, with k groups left, to split points into clusters that are as far apart as possible. About 15 minutes.
Stop with k groups left
Imagine splitting customers on a map into k delivery zones so that different zones are as far from each other as possible. Customers that are close should share a zone.
The cheapest-first process does exactly this if you stop it early. Start with every point as its own group, so n groups. Go through all pairs from closest to farthest, merging groups, and each merge lowers the group count by 1. Stop when only k groups remain.
links = [] links.append((gap, i, j)) links.sort()
- groups
- 6
Closest pair first: 3 and 4, a gap of 1. Merge them. Now 6 groups.
The gap is the next link
Once k groups remain, keep walking through the sorted pairs. Skip pairs whose two points are already in the same group, since those are inside a zone. The first pair that joins two different groups is the closest any two zones get.
That distance is the answer, called the spacing. It's the biggest gap you can force between zones, because any other split into k groups would put a closer pair into different zones.
groups -= 1
if groups == k:
return gapWith k groups left, the next closest pair has both points in the same group. What do you do?
- ASkip it and look at the next pair
- BReturn its distance as the spacing
- CMerge them anyway
Show the answer
Skip it and look at the next pair. Pairs inside one group don't cross a boundary, so they don't set the spacing.
Far-apart groups
points[i] = [x, y] is the position of a point. The distance between two points is the Manhattan distance |x1 − x2| + |y1 − y2|. Split all the points into exactly k non-empty groups. The spacing of a split is the smallest distance between two points that are in different groups. Return the largest spacing that any split into k groups can achieve.
points = [[1, 0], [2, 0], [4, 0], [9, 0], [10, 0], [20, 0]], k = 3 → 5
2 ≤ k ≤ points ≤ 300 · −10,000 ≤ x, y ≤ 10,000