There are n workers and n jobs; cost[i][j] is the cost of assigning worker i to job j. Assign each worker…

Question

There are n workers and n jobs; cost[i][j] is the cost of assigning worker i to job j. Assign each worker exactly one distinct job to minimize total cost. Return the minimum total cost. 1 <= n <= 12, 0 <= cost[i][j] <= 10^5.

Prep Room · Answer

### Intuition This is identical to a standard assignment problem but with size constraints $N \le 12$. An $O(N!)$ full permutation approach is prohibitively…

Assign workers jobs