PreviousNext
Coding/Graphs and trees

Minimum cost assignment

Write codeHard40 minUber and DoorDash style

Your task

You must assign n workers to n jobs, one worker per job. cost[i][j] is the cost of assigning worker i to job j. Return the minimum total cost of a complete assignment (a perfect matching). Constraints: 1 <= n <= 80, 0 <= cost[i][j] <= 10^6. A simple greedy or per-row minimum does NOT give the optimum.

Examples

min_assignment_cost(cost: list[list[int]]) -> int
Example 1
Inputmin_assignment_cost([[9, 2, 7], [6, 4, 3], [5, 8, 1]])
Output9