{x}
blog image

Maximum Number of Achievable Transfer Requests

We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It's 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. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.

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: 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

Solution Explanation: Maximum Achievable Transfer Requests

This problem asks to find the maximum number of employee transfer requests that can be fulfilled while ensuring that the net change in employees for each building is zero. The key insight is that the number of requests is relatively small (at most 16), allowing us to efficiently explore all possible combinations of requests using bit manipulation.

Approach: Bitmask Enumeration

The solution uses a bitmask to represent which requests are selected. Each bit in the mask corresponds to a request: a 1 indicates the request is selected, and a 0 indicates it's not. We iterate through all possible bitmasks (from 0 to 2m - 1, where m is the number of requests).

For each bitmask:

  1. Count Selected Requests: We count the number of 1s in the bitmask. This represents the number of requests selected in this combination.

  2. Check Feasibility: We simulate the selected requests to check if the net change in employees for each building is zero. This is done by creating an array cnt to track the change in employee count for each building. For each selected request [from, to], we decrement cnt[from] and increment cnt[to]. If, after processing all selected requests, all values in cnt are zero, the combination is feasible.

  3. Update Maximum: If the combination is feasible and the number of selected requests is greater than the current maximum, we update the maximum.

Time and Space Complexity Analysis

  • Time Complexity: O(2m * (m + n)), where m is the number of requests and n is the number of buildings. We iterate through 2m bitmasks. For each bitmask, we process at most m requests and check n building counts. The bitCount function has a constant time complexity.

  • Space Complexity: O(n). The space is dominated by the cnt array used to track building employee counts.

Code Implementation (Python)

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        m = len(requests)
        max_requests = 0
 
        for i in range(1 << m): # Iterate through all possible bitmasks
            selected_requests = []
            for j in range(m):
                if (i >> j) & 1:  #Check if j-th bit is set
                    selected_requests.append(requests[j])
 
            building_counts = [0] * n
            feasible = True
            for from_building, to_building in selected_requests:
                building_counts[from_building] -= 1
                building_counts[to_building] += 1
 
            for count in building_counts:
                if count != 0:
                    feasible = False
                    break
 
            if feasible:
                max_requests = max(max_requests, len(selected_requests))
 
        return max_requests

The code in other languages (Java, C++, Go, TypeScript, JavaScript, C#) follows a similar structure, adapting the bit manipulation and array handling to the specifics of each language. The core algorithm remains the same.