The problem
A depot has nl drivers and nr routes. Each allowed pair (worker, job) says that a driver can take a route. Give as many drivers as possible one route each, with no route given twice: a maximum matching. Return the pairs you choose.
pairs = [(0, 0), (0, 1), (1, 0), (2, 1),
(2, 2), (3, 2), (3, 3)]
matching(4, 4, pairs)
# [(0, 1), (1, 0), (2, 2), (3, 3)]
When several matchings are largest, any of them is accepted: the tests check that every pair is allowed, that no driver or route is used twice, and how many pairs there are.
Limits
- Up to 60,000 drivers, 60,000 routes and 120,000 pairs. The big tests have 3 to 4 seconds each.
- An augmenting path can be 10,000 steps long, so recursion is too deep.
- The last test (30,000 drivers, 90,000 pairs) needs Hopcroft-Karp (lesson 5); one search per free driver passes the rest.
Builds on FLOW-5 Bipartite matching.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Greedy is not enough | Not run | |
| 3 | More jobs than workers | Not run | |
| 4 | A worker with no jobs | Not run | |
| 5 | Repeated pairs | Not run | |
| 6 | No pairs | Not run | |
| 7 | A long chain | Not run | |
| 8 | 60,000 workers, 120,000 pairs | Not run | |
| 9 | 30,000 workers, 90,000 pairs | Not run |