Maximum Number of Achievable Transfer Requests
We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It is transfer season, and some employees want to change the building they reside in.
You are given an array requests where requests[i] = [fromi, toi] represents an employee's request to transfer from building fromi to building toi.
All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in.
Return the maximum number of achievable requests.
Example 1
Input
n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]Output
5The first five requests can be achieved by swaps among buildings 0, 1, and 2, while the request from building 3 to building 4 cannot be included without making the net changes nonzero.
Example 2
Input
n = 3, requests = [[0,0],[1,2],[2,1]]Output
3The employee in building 0 stays, and the employees in buildings 1 and 2 swap, so all requests are achievable.
Constraints
- 1 <= n <= 20
- 1 <= requests.length <= 16
- requests[i].length == 2
- 0 <= fromi, toi < n