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.
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int max_requests = 0;
7
8void backtrack(vector<int>& indegree, int start, int n, int requestsSize, int count, vector<vector<int>>& requests) {
9 if (start == requestsSize) {
10 for (int i = 0; i < n; ++i) {
11 if (indegree[i] != 0) return;
12 }
13 max_requests = max(max_requests, count);
14 return;
15 }
16
17 indegree[requests[start][0]]--;
18 indegree[requests[start][1]]++;
19 backtrack(indegree, start + 1, n, requestsSize, count + 1, requests);
20 indegree[requests[start][0]]++;
21 indegree[requests[start][1]]--;
22
23 backtrack(indegree, start + 1, n, requestsSize, count, requests);
24}
25
26int maximumRequests(int n, vector<vector<int>>& requests) {
27 vector<int> indegree(n, 0);
28 backtrack(indegree, 0, n, requests.size(), 0, requests);
29 return max_requests;
30}
31
32int main() {
33 vector<vector<int>> requests1 = {{0, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 0}, {3, 4}};
34 cout << maximumRequests(5, requests1) << endl;
35
36 vector<vector<int>> requests2 = {{0, 0}, {1, 2}, {2, 1}};
37 cout << maximumRequests(3, requests2) << endl;
38
39 vector<vector<int>> requests3 = {{0, 3}, {3, 1}, {1, 2}, {2, 0}};
40 cout << maximumRequests(4, requests3) << endl;
41
42 return 0;
43}This code uses a backtracking algorithm to explore all combinations of requests, updating building indegrees accordingly. If all indegrees return to zero, the number of requests in that combination is checked for the maximum count.
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.
public class MaxAchievableRequestsBitmask {
public int MaximumRequests(int n, int[][] requests) {
int m = requests.Length;
int maxRes = 0;
for (int mask = 0; mask < (1 << m); mask++) {
int[] indegree = new int[n];
int num_requests = 0;
for (int i = 0; i < m; i++) {
if ((mask & (1 << i)) != 0) {
indegree[requests[i][0]]--;
indegree[requests[i][1]]++;
num_requests++;
}
}
bool valid = true;
foreach (var deg in indegree) {
if (deg != 0) {
valid = false;
break;
}
}
if (valid) {
maxRes = Math.Max(maxRes, num_requests);
}
}
return maxRes;
}
public static void Main(string[] args) {
MaxAchievableRequestsBitmask marb = new MaxAchievableRequestsBitmask();
int[][] requests1 = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, 1}, new int[] {1, 2}, new int[] {2, 0}, new int[] {3, 4} };
Console.WriteLine(marb.MaximumRequests(5, requests1));
int[][] requests2 = new int[][] { new int[] {0, 0}, new int[] {1, 2}, new int[] {2, 1} };
Console.WriteLine(marb.MaximumRequests(3, requests2));
int[][] requests3 = new int[][] { new int[] {0, 3}, new int[] {3, 1}, new int[] {1, 2}, new int[] {2, 0} };
Console.WriteLine(marb.MaximumRequests(4, requests3));
}
}This C# approach applies masks to iterate all possible subsets of requests, uses an indegree array for balance evaluation, and stores the maximum number of feasible requests achieved.