Funcia
Lv.3bipartite-matchinggraph

Worker-Task Matching

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

There are workers workers (numbered from 0) and tasks tasks (numbered from 0). can[i] = [w, t] means worker w is able to do task t.

Each worker takes at most one task and each task goes to at most one worker, and a worker may only get a task they can do. Return the maximum number of tasks that can be assigned at the same time.

Examples

workerstaskscanresult
33[[0, 0], [0, 1], [1, 0], [2, 1]]2
33[[0, 0], [0, 1], [1, 1], [1, 2], [2, 0]]3
24[]0

Example 2 — Worker 0 → task 1, worker 1 → task 2, worker 2 → task 0. Giving task 0 to worker 0 first would leave worker 2 idle, so assignments must be revised along the way.

Efficiency

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

Function signature

solution(workers: int, tasks: int, can: int[][]) → int

Constraints

  • 1≤1 \le workers, tasks ≤3,000\le 3{,}000, 0≤E=0 \le E = can.length ≤50,000\le 50{,}000
  • 0≤0 \le w << workers, 0≤0 \le t << tasks; the same pair may appear more than once.

Expected complexity

Time
O(E * sqrt(V))
Space
O(V + E)

Examples

workerstaskscanExpected
33[[0,0],[0,1],[1,0],[2,1]]2
33[[0,0],[0,1],[1,1],[1,2],[2,0]]3
24[]0

Hint

Hint

This is maximum bipartite matching. From each free worker search for an augmenting path (task free, or its current worker can be moved to another task) and flip it. Kuhn's algorithm over adjacency lists is O(V⋅E)O(V \cdot E); Hopcroft–Karp finds many shortest augmenting paths per BFS phase in O(EV)O(E\sqrt{V}). Scanning an adjacency matrix for every augmentation is O(V3)O(V^3) 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.131000 msderived
Java 251132 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

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

No result yet. Run or submit your code.