Leetcode

Maximum Number of Achievable Transfer Requests

May 26, 2022 by aAshish

  • Time:O(n \cdot 2^|\texttt{requests}|)
  • Space:O(n + |\texttt{requests}|)

C++

 
class Solution {
 public:
  int maximumRequests(int n, vector<vector<int>>& requests) {
    int ans = 0;
    vector<int> degree(n);  // degree[i] := degree of building i

    function<void(int, int)> dfs = [&](int i, int processedReqs) {
      if (i == requests.size()) {
        if (all_of(begin(degree), end(degree), [](int d) { return d == 0; }))
          ans = max(ans, processedReqs);
        return;
      }

      // skip requests[i]
      dfs(i + 1, processedReqs);

      // process requests[i]
      --degree[requests[i][0]];
      ++degree[requests[i][1]];
      dfs(i + 1, processedReqs + 1);
      --degree[requests[i][1]];
      ++degree[requests[i][0]];
    };

    dfs(0, 0);

    return ans;
  }
};

JAVA

 
class Solution {
  public int maximumRequests(int n, int[][] requests) {
    dfs(0, 0, requests, new int[n]);

    return ans;
  }

  private int ans = 0;

  private void dfs(int i, int processedReqs, int[][] requests, int[] degree) {
    if (i == requests.length) {
      if (Arrays.stream(degree).allMatch(d -> d == 0))
        ans = Math.max(ans, processedReqs);
      return;
    }

    // skip requests[i]
    dfs(i + 1, processedReqs, requests, degree);

    // process requests[i]
    --degree[requests[i][0]];
    ++degree[requests[i][1]];
    dfs(i + 1, processedReqs + 1, requests, degree);
    --degree[requests[i][1]];
    ++degree[requests[i][0]];
  }
}