Worker-Task Matching
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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
| workers | tasks | can | result |
|---|---|---|---|
3 | 3 | [[0, 0], [0, 1], [1, 0], [2, 1]] | 2 |
3 | 3 | [[0, 0], [0, 1], [1, 1], [1, 2], [2, 0]] | 3 |
2 | 4 | [] | 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
-
workers,tasks,can.length -
wworkers,ttasks; the same pair may appear more than once.
Expected complexity
- Time
- O(E * sqrt(V))
- Space
- O(V + E)
Examples
| workers | tasks | can | Expected |
|---|---|---|---|
3 | 3 | [[0,0],[0,1],[1,0],[2,1]] | 2 |
3 | 3 | [[0,0],[0,1],[1,1],[1,2],[2,0]] | 3 |
2 | 4 | [] | 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 ; Hopcroft–Karp finds many shortest augmenting paths per BFS phase in . Scanning an adjacency matrix for every augmentation is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1132 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |