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.
1using System;
2using System.Collections.Generic;
3
4public class MaxAchievableRequests {
5 private int max_requests = 0;
6
7 public void Backtrack(int[] indegree, int start, int n, int count, int[][] requests) {
8 if (start == requests.Length) {
9 for (int i = 0; i < n; i++) {
10 if (indegree[i] != 0) return;
11 }
12 max_requests = Math.Max(max_requests, count);
13 return;
14 }
15
16 indegree[requests[start][0]]--;
17 indegree[requests[start][1]]++;
18 Backtrack(indegree, start + 1, n, count + 1, requests);
19 indegree[requests[start][0]]++;
20 indegree[requests[start][1]]--;
21
22 Backtrack(indegree, start + 1, n, count, requests);
23 }
24
25 public int MaximumRequests(int n, int[][] requests) {
26 int[] indegree = new int[n];
27 Backtrack(indegree, 0, n, 0, requests);
28 return max_requests;
29 }
30
31 public static void Main(string[] args) {
32 MaxAchievableRequests mar = new MaxAchievableRequests();
33 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} };
34 Console.WriteLine(mar.MaximumRequests(5, requests1));
35
36 int[][] requests2 = new int[][] { new int[] {0, 0}, new int[] {1, 2}, new int[] {2, 1} };
37 Console.WriteLine(mar.MaximumRequests(3, requests2));
38
39 int[][] requests3 = new int[][] { new int[] {0, 3}, new int[] {3, 1}, new int[] {1, 2}, new int[] {2, 0} };
40 Console.WriteLine(mar.MaximumRequests(4, requests3));
41 }
42}The C# solution employs a recursive backtracking method that updates balance with an indegree array, exploring all possibilities to maximize the number of valid 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.
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.