Vultr DocsLatest Content

Maximum Number of Achievable Transfer Requests

Updated on 10 June, 2025
Maximum Number of Achievable Transfer Requests header image

Problem Statement

In a scenario where several buildings are each filled with employees, we encounter a period referred to as the transfer season. During this season, employees may request to move from their current building to another. This scenario is captured in the form of an array called requests, where each element [fromi, toi] indicates an employee's desire to transfer from building fromi to building toi.

A crucial aspect to consider is that all buildings are occupied to their full capacity. For any set of transfer requests to be feasible, it is essential that the net change of employees in each building remains zero, meaning the number of employees leaving a building must equal the number of employees entering it.

The challenge lies in determining the maximum number of these transfer requests that can be simultaneously fulfilled without violating the condition of maintaining net zero change in the employee count per building.

Examples

Example 1

Input:

n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]

Output:

5

Explantion:

Let's see the requests:
From building 0 we have employees x and y and both want to move to building 1.
From building 1 we have employees a and b and they want to move to buildings 2 and 0 respectively.
From building 2 we have employee z and they want to move to building 0.
From building 3 we have employee c and they want to move to building 4.
From building 4 we don't have any requests.
We can achieve the requests of users x and b by swapping their places.
We can achieve the requests of users y, a and z by swapping the places in the 3 buildings.

Example 2

Input:

n = 3, requests = [[0,0],[1,2],[2,1]]

Output:

3

Explantion:

Let's see the requests:
From building 0 we have employee x and they want to stay in the same building 0.
From building 1 we have employee y and they want to move to building 2.
From building 2 we have employee z and they want to move to building 1.
We can achieve all the requests.

Example 3

Input:

n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]

Output:

4

Constraints

  • 1 <= n <= 20
  • 1 <= requests.length <= 16
  • requests[i].length == 2
  • 0 <= fromi, toi < n

Approach and Intuition

The problem can essentially be viewed as a graph traversal problem where each building represents a node and each request represents a directed edge from one node to another. The goal is to ascertain a subgraph (subset of requests) where every node (building) has balanced in-degrees and out-degrees (equal number of people moving in and out). Here's how one might approach solving it:

  1. Represent the Requests as a Graph:

    • For each request [fromi, toi], consider it as a directed edge from node fromi to node toi.

  2. Check Feasibility of Subsets of Requests:

    • Use a depth-first search (DFS) or a bit manipulation technique to explore all possible subsets of the requests.
    • For each subset, track the changes in incoming and outgoing employees for each building.

  3. Validate Each Subset:

    • A valid subset is one where, for every building, the count of incoming employees equals the count of outgoing employees.

  4. Maximize the Accepted Requests:

    • Keep track of the maximum number of requests in any valid subset found during the exploration.

Intuitive Understanding:

  • The problem can be likened to finding the maximum number of balanced transactions in a network where each transaction is a potential employee move.
  • We are effectively seeking the largest cycle or set of cycles within a directed graph formed by the requests, such that these cycles cover the majority of the requests and ensure balance in each node (building).

This way, the problem, while computationally heavy due to its potential combinatorial nature, especially with the constraint bounds given, is tractable using a backtracking approach that efficiently explores possible subsets of requests to find the maximum feasible set.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    int solve(int buildings, vector<vector<int>>& reqs) {
        int res = 0; 
        // Explore all possible subsets of requests
        for (int comb = 0; comb < (1 << reqs.size()); comb++) {
            vector<int> balance(buildings, 0);
            int lastIndex = reqs.size() - 1;
            // Calculate number of requests selected in the current combination
            int countSelectedRequests = __builtin_popcount(comb);
            
            // Skip this combination if it has fewer requests than the best found so far
            if (countSelectedRequests <= res) {
                continue;
            }
            
            // Adjust the balance of buildings according to selected requests
            for (int cur = comb; cur > 0; cur >>= 1, lastIndex--) {
                if (cur & 1) {
                    balance[reqs[lastIndex][0]]--;
                    balance[reqs[lastIndex][1]]++;
                }
            }
            
            // Check if the current selection of requests is valid, i.e., every building is balanced
            bool isValid = true;
            for (int i = 0; i < buildings; i++) {
                if (balance[i] != 0) {
                    isValid = false;
                    break;
                }
            }
            
            // Update the best result if the current selection is valid
            if (isValid)  {
                res = countSelectedRequests;
            }
        }
        
        return res;
    }
};

The C++ solution provided aims to solve a problem where the objective is to determine the maximum number of achievable transfer requests between buildings based on given requests. The solution adopts a brute-force approach, leveraging bitwise operations to explore all possible combinations of these requests.

Here's a breakdown of how the code operates:

  • A solve function is defined that accepts two parameters: buildings, the number of buildings, and reqs, a list of requests where each is represented as a vector with two integers indicating the source and destination buildings.
  • The variable res is initialized to zero, used to keep track of the highest number of achievable requests.
  • The solution employs a loop through all possible subsets of requests using a bit manipulation technique. This is done by iterating from 0 to (1 << reqs.size())-1, representing all combinations of possible request selections.
  • For every combination, a balance vector is initialized to register the net number of transfers to and from each building.
  • The countSelectedRequests variable holds the number of requests involved in the current subset, calculated using the __builtin_popcount function which counts the number of 1-bits.
  • Subsets with a count of selected requests not exceeding the current maximum res are skipped.
  • For valid subsets (where net transfers for all buildings are zero), the current count of selected requests is compared with the maximum recorded in res, and if higher, updates res.
  • Finally, the function returns res, the maximum number of achievable requests.

This method ensures a complete search through all combinations, guaranteeing the discovery of the optimal number of requests that can be simultaneously satisfied, given the condition that all buildings must have balanced transfers. The solution's time complexity is primarily affected by the number of request combinations, making it exponential in terms of the number of requests due to the subset exploration using bit manipulation.

java 
class Solution {
    public int maxRequests(int buildingCount, int[][] requestsArray) {
        int maxAccepted = 0;

        for (int subset = 0; subset < (1 << requestsArray.length); subset++) {
            int[] netChange = new int[buildingCount];
            int index = requestsArray.length - 1;
            int numRequests = Integer.bitCount(subset);

            if (numRequests <= maxAccepted) {
                continue;
            }

            for (int sub = subset; sub > 0; sub >>= 1, index--) {
                if ((sub & 1) == 1) {
                    netChange[requestsArray[index][0]]--;
                    netChange[requestsArray[index][1]]++;
                }
            }

            boolean isValid = true;
            for (int j = 0; j < buildingCount; j++) {
                if (netChange[j] != 0) {
                    isValid = false;
                    break;
                }
            }

            if (isValid) {
                maxAccepted = numRequests;
            }
        }

        return maxAccepted;
    }
}

This Java solution is designed to determine the maximum number of achievable transfer requests for a given set of buildings and requests. The implementation works by considering every possible subset of requests using bit manipulation to enable or disable particular requests based on the bits of an integer.

  • The code begins with maxRequests, which takes buildingCount and a two-dimensional requestsArray as parameters. Here, buildingCount represents the number of buildings, and requestsArray contains pairs where each pair defines a transfer request from one building to another.
  • A variable maxAccepted is initialized to zero, which will store the maximum number of achievable requests.
  • It iterates over all possible subsets of requests using a loop that ranges from 0 to (1 << requestsArray.length), effectively generating each subset by treating the array index as a bitmask.
  • Within this loop, the netChange array calculates the net effect of the requests in each subset on each building.
  • To assess if a requests subset is valid, the net change for each building after applying all the requests in the subset must be zero, indicating all requested transfers are internally balanced among buildings.

The heart of the algorithm relies on the principle of backtracking and state exploration, representing each subset of requests as binary numbers where each bit corresponds to a request being included (1) or excluded (0). This ensures that all possible combinations of requests are considered.

The validity of each subset is checked for whether the effect of all requests results in a net zero change (i.e., requests balance each other out). If a valid subset is larger than the previously found subsets, it updates maxAccepted. The loop continues until all possible subsets are evaluated, guaranteeing that the maximum possible subset (in terms of the number of requests) is found.

Finally, the function returns the variable maxAccepted, which is the maximum number of internally balanced requests that can be achieved.

Comments

No comments yet.