Sponsored
Sponsored
This approach involves generating all subsets of requests and checking if they result in a balanced transfer of employees among all buildings. We maximize the number of requests in the subset where the number of inputs equals the number of outputs for every building.
Time Complexity: O(2^R * N), where R is the number of requests and N is the number of buildings.
Space Complexity: O(N), mainly because of the indegree array used for tracking the net inflow for each building.
1def backtrack(indegree, start, n, count, requests):
2 global max_requests
3 if start == len(requests):
4 if all(x == 0 for x in indegree):
5 max_requests = max(max_requests, count)
6 return
7
8 # Choose the current request
9 indegree[requests[start][0]] -= 1
10 indegree[requests[start][1]] += 1
11 backtrack(indegree, start + 1, n, count + 1, requests)
12
13 # Backtrack
14 indegree[requests[start][0]] += 1
15 indegree[requests[start][1]] -= 1
16
17 # Skip the current request
18 backtrack(indegree, start + 1, n, count, requests)
19
20
21def maximumRequests(n, requests):
22 global max_requests
23 max_requests = 0
24 indegree = [0] * n
25 backtrack(indegree, 0, n, 0, requests)
26 return max_requests
27
28# Testing the implementation
29print(maximumRequests(5, [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]))
30print(maximumRequests(3, [[0,0],[1,2],[2,1]]))
31print(maximumRequests(4, [[0,3],[3,1],[1,2],[2,0]]))The Python implementation uses recursion to explore each subset of requests. It updates a global maximum count when all building transfers result in zero net transfer.
This approach uses dynamic programming with bitmasking, reducing redundant calculations by storing results of previously computed states. It leverages the idea of subsets, where we test combinations represented as binary masks and check balance conditions for employee transfers.
Time Complexity: O(2^R * R * N) where R is the number of requests and N is the number of buildings.
Space Complexity: O(2^R) for dp array holding states by subsets of requests.
The JavaScript implementation uses a bitmask dynamic programming strategy to iterate through each request combination, leveraging an indegree array to guarantee all buildings maintain zero transfers, ensuring valid results.