Maximum Number Of Achievable Transfer Requests
01 · Problem
There are n buildings numbered 0 to n - 1. Each building is currently full, and employees have filed transfer requests. requests[i] = [from_i, to_i] means one employee wants to move out of building from_i and into building to_i (they may be the same building).
You may approve any subset of the requests, as long as, after approving them, every building ends up with exactly as many people as it started with. In other words, for every building the number of approved requests leaving it equals the number of approved requests arriving at it.
Return the largest number of requests that can be approved. Approving no requests is always valid, so the answer is at least 0.
02 · Examples
n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
5
Approve [0,1],[1,0] (a swap) and [0,1],[1,2],[2,0] (a cycle). Every building's inflow equals its outflow. [3,4] cannot be approved because nobody moves back into building 3.
n = 3, requests = [[0,0],[1,2],[2,1]]
3
[0,0] keeps an employee in place, and [1,2] with [2,1] is a swap. All three can be approved.
n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
4
The four requests form one cycle 0 -> 3 -> 1 -> 2 -> 0, so approving all of them keeps every building balanced.
03 · Constraints
- 01`1 <= n <= 20`
- 02`1 <= requests.length <= 16`
- 03`requests[i].length == 2`
- 04`0 <= from_i, to_i < n`
04 · Optimal complexity
- Time
- O(2^m * n)
- Space
- O(n + m)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.