Maximum applicant job assignment
There are n applicants and m jobs. You are given an adjacency list where allowed[i] is the list of job indices (0..m-1) applicant i can do. Each applicant can be assigned at most one job and each job to at most one applicant. Return the maximum number of applicants that can be assigned a job (the size of a maximum bipartite matching).
Implement
max_bipartite_matching(n: int, m: int, allowed: list[list[int]]) → intExamples
in
[3,3,[[0,1],[0],[0,2]]]out3What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 40 min
solution.py
InputExpectedGot
[3,3,[[0,1],[0],[0,2]]]3not run yetsample