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.
The C solution uses a bitmask dynamic programming approach. It stores intermediate results of various combinations of requests in a dp array. The mask iterates over possible subsets of requests, updating indegree array and maximizing valid request count.