Crew Job Hungarian Problem

Crew Job Hungarian Problem — ExecCode Hard DSA Practice

Solve the Crew Job Hungarian problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

n crews and n jobs. cost[i][j] is the hours if crew i takes job j. Each crew gets one job, each job one crew. The Hungarian algorithm (or min-cost matching / MCMF on a bipartite graph) finds the assignment of minimum total cost. Return that minimum total. The matrix is n by n. You are given: cost — n x n hours matrix Return minimum assignment cost. Costs are not required to satisfy triangle inequality.

Examples

Input {'cost': [[3, 1], [2, 4]]}; Output 3. Input {'cost': [[5]]}; Output 5. Input {'cost': [[1, 2, 3], [4, 5, 6], [7, 8, 9]]}; Output 15

Constraints

Square matrix Empty matrix 0

Practice Crew Job Hungarian free on ExecCode. Browse DSA problems, topic map, and placement guides.