#1595
Minimum Cost to Connect Two Groups of Points
candidate master · 1435 · lc hard +32 · verified · 49.6% accepted · 493 likes · top 37%
Description
Two groups of points must be fully interconnected: every point in the first group must connect to at least one in the second, and vice versa. A cost matrix gives the connection cost between each pair. Return the minimum total cost to achieve this full interconnection.
Example 1:
Input: cost = [[15, 96], [36, 2]]
Output: 17
Explanation: The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.
Example 2:
Input: cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
Output: 4
Explanation: The optimal way of connecting the groups is:
1--A
2--B
2--C
3--A
This results in a total cost of 4.
Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.
Example 3:
Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
Output: 10
Code
1
2
3