hardGraphsPure DSA~40 min
Minimum Cabling To Connect Nodes
A set of rack positions must be linked into one connected network. Laying cable between two racks costs their Manhattan distance. Find the minimum total cable length so every rack is reachable from every other.
Problem
Given n points on a 2-D plane, connect all points so they are mutually reachable, where the cost between two points is their Manhattan distance |x1−x2| + |y1−y2|. Return the minimum total cost (the weight of a minimum spanning tree).
Input
An array points of n coordinate pairs (1 ≤ n ≤ 1000, −10^6 ≤ coord ≤ 10^6).
Output
An integer: the minimum total connection cost.
Constraints
- 1 ≤ n ≤ 1000
- All point coordinates are distinct or may coincide
- Edges are implicit between every pair (complete graph)
Examples
Example 1
Input
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output
20
An MST over the Manhattan-distance complete graph totals 20.
Example 2
Input
points = [[3,12],[-2,5],[-4,1]]
Output
18
Connecting the three points cheapest costs 18.