hardBacktrackingPure DSA~30 min
Maximum Achievable Transfer Requests
Employees request to move between buildings. A transfer plan is valid only if every building ends with the same headcount it started with (net zero change). Approve the most requests possible.
Problem
Given n buildings and a list requests where requests[i] = [from_i, to_i] means one person wants to move from building from_i to to_i, return the maximum number of requests that can be approved such that every building's net change is zero.
Input
An integer n and an array requests of [from, to] pairs.
Output
An integer: the maximum number of simultaneously satisfiable requests.
Constraints
- 1 <= n <= 20
- 1 <= requests.length <= 16
- 0 <= from_i, to_i < n
Examples
Example 1
Input
n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
Output
5
Approving all but the unmatched [3,4] keeps every building balanced.
Example 2
Input
n = 3, requests = [[0,0],[1,2],[2,1]]
Output
3
The self-loop plus the mutual swap all keep net change zero.