Funcia
Lv.4assignment-problemhungarian-algorithmmatching

Minimum-Cost Task Assignment (Large)

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

N employees must each take exactly one of N tasks, and every task must go to exactly one employee. Assigning task j to employee i costs cost[i][j]. Return the minimum total cost.

Examples

costresult
[[4, 1, 3], [2, 0, 5], [3, 2, 2]]5
[[7]]7
[[1, 2], [3, 6]]5

Example 1 — 1 + 2 + 2; taking the cheapest cell cost[1][1] = 0 forces a total of at least 6.

Example 2 — one employee, one task.

Example 3 — greedily taking cost[0][0] = 1 gives 7, but 2 + 3 = 5.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(cost: int[][]) → int

Constraints

  • 1≤N=1 \le N = cost.length ≤300\le 300, every cost[i].length =N= N
  • 0≤0 \le cost[i][j] ≤1,000,000\le 1{,}000{,}000

Expected complexity

Time
O(N^3)
Space
O(N)

Examples

costExpected
[[4,1,3],[2,0,5],[3,2,2]]5
[[7]]7
[[1,2],[3,6]]5

Hint

Hint

This is the assignment problem; use the Hungarian algorithm with potentials u[i] + v[j] <= cost[i][j]. Add employees one at a time: grow an alternating tree over tight cells, and when stuck raise u on tree rows and lower v on tree columns by the minimum slack delta, until a free task is reached and the alternating path is flipped. Maintaining the per-column minimum slack minv[j] incrementally gives O(N2)O(N^2) per employee and O(N3)O(N^3) overall; recomputing delta from scratch every step is O(N4)O(N^4) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.133226 msderived
Java 251070 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance605verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.