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.
1public class MaxAchievableRequests {
2 int max_requests = 0;
3
4 public void backtrack(int[] indegree, int start, int n, int count, int[][] requests) {
5 if (start == requests.length) {
6 for (int i = 0; i < n; i++) {
7 if (indegree[i] != 0) return;
8 }
9 max_requests = Math.max(max_requests, count);
10 return;
11 }
12
13 indegree[requests[start][0]]--;
14 indegree[requests[start][1]]++;
15 backtrack(indegree, start + 1, n, count + 1, requests);
16 indegree[requests[start][0]]++;
17 indegree[requests[start][1]]--;
18
19 backtrack(indegree, start + 1, n, count, requests);
20 }
21
22 public int maximumRequests(int n, int[][] requests) {
23 int[] indegree = new int[n];
24 backtrack(indegree, 0, n, 0, requests);
25 return max_requests;
26 }
27
28 public static void main(String[] args) {
29 MaxAchievableRequests mar = new MaxAchievableRequests();
30 int[][] requests1 = {{0, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 0}, {3, 4}};
31 System.out.println(mar.maximumRequests(5, requests1));
32
33 int[][] requests2 = {{0, 0}, {1, 2}, {2, 1}};
34 System.out.println(mar.maximumRequests(3, requests2));
35
36 int[][] requests3 = {{0, 3}, {3, 1}, {1, 2}, {2, 0}};
37 System.out.println(mar.maximumRequests(4, requests3));
38 }
39}The Java solution similarly implements backtracking by iterating through each request and tracking its status in the indegree array. The maximum number of requests that can achieve a balanced network is computed.
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.