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.
1function backtrack(indegree, start, n, count, requests) {
2 if (start === requests.length) {
3 if (indegree.every(x => x === 0)) {
4 maxRequests = Math.max(maxRequests, count);
5 }
6 return;
7 }
8
9 indegree[requests[start][0]]--;
10 indegree[requests[start][1]]++;
11 backtrack(indegree, start + 1, n, count + 1, requests);
12
13 indegree[requests[start][0]]++;
14 indegree[requests[start][1]]--;
15 backtrack(indegree, start + 1, n, count, requests);
16}
17
18let maxRequests;
19
20function maximumRequests(n, requests) {
21 maxRequests = 0;
22 const indegree = Array(n).fill(0);
23 backtrack(indegree, 0, n, 0, requests);
24 return maxRequests;
25}
26
27// Testing the function
28console.log(maximumRequests(5, [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]));
29console.log(maximumRequests(3, [[0,0],[1,2],[2,1]]));
30console.log(maximumRequests(4, [[0,3],[3,1],[1,2],[2,0]]));The JavaScript implementation uses recursion and an indegree array to track requests, measuring maximum achievable requests only when all indegrees return to zero after exploring all combinations.
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 Java implementation uses bitmask dynamic programming by representing subsets as masks. It verifies validity by ensuring all building indices are zero after applying requests in the mask, updating the maximal achieved request count.