Minimum Cost to Connect Two Groups of Points

Challenge Points: 30

Level: Hard

You are given two sets of points.
Set 1 contains size1 points, and Set 2 contains size2 points (and size1 ≥ size2).

You also get a matrix where cost[i][j] tells how much it costs to connect point i from Set 1 to point j from Set 2.

To fully connect the groups:

Every point in Set 1 must be linked to at least one point in Set 2
Every point in Set 2 must be linked to at least one point in Set 1

There is no limit on how many connections a single point may have.

Your task is to find the minimum total cost required so that both groups become fully connected.

Example 1:

Input: cost = [[4, 7], [2, 6]]

Output: 8

Explanation:

Best way: Point1 → B (cost 7) Point2 → A (cost 2) Total = 9 But better way: Point1 → A (4) Point2 → B (6) Total = 10 Actually best: Point1 → A (4) Point2 → A (2) Every point in group2 is still covered using extra connection: Point1 → B (7) Minimum cost = 8