Daily bit(e) of C++ | Maximum number of office transfers
Daily bit(e) of C++ #324, Common interview problem: Maximum number of office transfers.
Today, we will look at a common C++ interview problem: Maximum number of office transfers.
Given the number of offices and a list of single-person transfer requests between (or within a building, return the maximum number of possible requests that can be satisfied without changing the occupancy of offices.
For example for three offices and the requests {{0,1},{0,2},{1,2},{1,2},{2,0}} the maximum is three requests: {{0,1},{1,2},{2,0}}.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/5hK9jY3er.
Solution
This is a variant of the NP-hard Bin packing problem, so there is no point in looking for an efficient solution. Our best bet is backtracking, iterating over all possibilities.
We can iterate over possibilities by recursing over each request and either picking it or not. At the tail end of our recursion, we can check whether the occupancy of our offices remained the same (by checking the total difference for each building) and keep track of our best solution (most approved requests).
