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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int max_requests;
6
7void backtrack(int* indegree, int start, int n, int total_requests, int count, int (*requests)[2], int requestsSize) {
8 if (start == requestsSize) {
9 // Check balance for all buildings
10 for (int i = 0; i < n; i++) {
11 if (indegree[i] != 0) {
12 return;
13 }
14 }
15 if (count > max_requests) {
16 max_requests = count;
17 }
18 return;
19 }
20
21 // Choose the current request
22 indegree[requests[start][0]]--;
23 indegree[requests[start][1]]++;
24 backtrack(indegree, start + 1, n, total_requests, count + 1, requests, requestsSize);
25
26 // Backtrack
27 indegree[requests[start][0]]++;
28 indegree[requests[start][1]]--;
29
30 // Skip the current request
31 backtrack(indegree, start + 1, n, total_requests, count, requests, requestsSize);
32}
33
34int maximumRequests(int n, int** requests, int requestsSize, int* requestsColSize) {
35 int indegree[n];
36 memset(indegree, 0, sizeof(indegree));
37 max_requests = 0;
38 backtrack(indegree, 0, n, requestsSize, 0, (int (*)[2])requests, requestsSize);
39 return max_requests;
40}
41
42int main() {
43 int requests1[][2] = {{0, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 0}, {3, 4}};
44 int requestsSize1 = 6;
45 int requests1ColumnSize = 2;
46 printf("%d\n", maximumRequests(5, (int **)requests1, requestsSize1, &requests1ColumnSize));
47
48 int requests2[][2] = {{0, 0}, {1, 2}, {2, 1}};
49 int requestsSize2 = 3;
50 int requests2ColumnSize = 2;
51 printf("%d\n", maximumRequests(3, (int **)requests2, requestsSize2, &requests2ColumnSize));
52
53 int requests3[][2] = {{0, 3}, {3, 1}, {1, 2}, {2, 0}};
54 int requestsSize3 = 4;
55 int requests3ColumnSize = 2;
56 printf("%d\n", maximumRequests(4, (int **)requests3, requestsSize3, &requests3ColumnSize));
57
58 return 0;
59}This implementation uses backtracking. We use an indegree array to track the net transfer requests at each building. We consider each request to either choose or not choose a request while backtracking. We update maximum requests when all buildings are balanced at zero net requests.
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.
1
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.