Minimum Cost to Connect Two Groups of Points
You are given two groups of points where the first group has size1 points, the second group has size2 points, and size1 >= size2.
The cost of the connection between any two points is given in a size1 x size2 matrix where cost[i][j] is the cost of connecting point i of the first group and point j of the second group. The groups are connected if each point in both groups is connected to one or more points in the opposite group. In other words:
- Each point in the first group must be connected to at least one point in the second group.
- Each point in the second group must be connected to at least one point in the first group.
Return the minimum cost it takes to connect the two groups.
Example 1
Input
cost = [[15,96],[36,2]]Output
17Connecting point 1 to A and point 2 to B gives a total cost of 15 + 2 = 17, which is optimal.
Example 2
Input
cost = [[1,3,5],[4,1,1],[1,5,3]]Output
4The optimal connections have total cost 1 + 1 + 1 + 1 = 4, and multiple connections to the same point are allowed.
Constraints
- size1 == cost.length
- size2 == cost[i].length
- 1 <= size1, size2 <= 12
- size1 >= size2
- 0 <= cost[i][j] <= 100
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.