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#include <vector>
#include <cstring>
using namespace std;
int maximumRequests(int n, vector<vector<int>>& requests) {
int m = requests.size();
vector<int> dp(1 << m, 0);
int maxRes = 0;
for (int mask = 0; mask < (1 << m); mask++) {
vector<int> indegree(n, 0);
int cnt = 0;
for (int i = 0; i < m; i++) {
if (mask & (1 << i)) {
cnt++;
indegree[requests[i][0]]--;
indegree[requests[i][1]]++;
}
}
bool valid = true;
for (int j = 0; j < n; j++) {
if (indegree[j] != 0) {
valid = false;
break;
}
}
if (valid) {
dp[mask] = cnt;
maxRes = max(maxRes, cnt);
}
}
return maxRes;
}
int main() {
vector<vector<int>> requests1 = {{0, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 0}, {3, 4}};
cout << maximumRequests(5, requests1) << endl;
vector<vector<int>> requests2 = {{0, 0}, {1, 2}, {2, 1}};
cout << maximumRequests(3, requests2) << endl;
vector<vector<int>> requests3 = {{0, 3}, {3, 1}, {1, 2}, {2, 0}};
cout << maximumRequests(4, requests3) << endl;
return 0;
}The C++ implementation uses a bitmask dynamic programming approach that evaluates each possible subset of requests, ensuring balance by leveraging the indegree array. Valid subsets update request counts in dp for maximum results.