You are given an n x n cost matrix where cost[i][j] is the cost of assigning agent i to task j. Assign every…

Question

You are given an n x n cost matrix where cost[i][j] is the cost of assigning agent i to task j. Assign every agent to exactly one distinct task (a perfect matching) so the total cost is minimized, and return that minimum total cost. All costs are non-negative integers. Constraints: 1 <= n <= 8.

Prep Room · Answer

### Intuition We need to pair up $n$ agents with $n$ tasks to minimize the total cost. Since $n$ is very small ($n \le 8$), we can explore all possible…

Assignment problem minimum cost