{"id":7429,"date":"2020-09-27T11:19:02","date_gmt":"2020-09-27T18:19:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7429"},"modified":"2020-09-27T11:36:01","modified_gmt":"2020-09-27T18:36:01","slug":"leetcode-1601-maximum-number-of-achievable-transfer-requests","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1601-maximum-number-of-achievable-transfer-requests\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1601. Maximum Number of Achievable Transfer Requests"},"content":{"rendered":"\n

We have n<\/code> buildings numbered from 0<\/code> to n - 1<\/code>. Each building has a number of employees. It’s transfer season, and some employees want to change the building they reside in.<\/p>\n\n\n\n

You are given an array requests<\/code> where requests[i] = [fromi<\/sub>, toi<\/sub>]<\/code> represents an employee’s request to transfer from building fromi<\/sub><\/code> to building toi<\/sub><\/code>.<\/p>\n\n\n\n

All buildings are full<\/strong>, so a list of requests is achievable only if for each building, the net change in employee transfers is zero<\/strong>. This means the number of employees leaving<\/strong> is equal<\/strong> to the number of employees moving in<\/strong>. For example if n = 3<\/code> and two employees are leaving building 0<\/code>, one is leaving building 1<\/code>, and one is leaving building 2<\/code>, there should be two employees moving to building 0<\/code>, one employee moving to building 1<\/code>, and one employee moving to building 2<\/code>.<\/p>\n\n\n\n

Return the maximum number of achievable requests<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]\nOutput:<\/strong> 5\nExplantion:<\/strong> Let's see the requests:\nFrom building 0 we have employees x and y and both want to move to building 1.\nFrom building 1 we have employees a and b and they want to move to buildings 2 and 0 respectively.\nFrom building 2 we have employee z and they want to move to building 0.\nFrom building 3 we have employee c and they want to move to building 4.\nFrom building 4 we don't have any requests.\nWe can achieve the requests of users x and b by swapping their places.\nWe can achieve the requests of users y, a and z by swapping the places in the 3 buildings.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 3, requests = [[0,0],[1,2],[2,1]]\nOutput:<\/strong> 3\nExplantion:<\/strong> Let's see the requests:\nFrom building 0 we have employee x and they want to stay in the same building 0.\nFrom building 1 we have employee y and they want to move to building 2.\nFrom building 2 we have employee z and they want to move to building 1.\nWe can achieve all the requests. <\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]\nOutput:<\/strong> 4\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= n <= 20<\/code><\/li>
  • 1 <= requests.length <= 16<\/code><\/li>
  • requests[i].length == 2<\/code><\/li>
  • 0 <= fromi<\/sub>, toi<\/sub> < n<\/code><\/li><\/ul>\n\n\n\n
    Solution: Combination<\/strong><\/h2>\n\n\n\n
    Try all combinations: O(2^n * (r + n))
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maximumRequests(int n, vector>& requests) {\n    const int r = requests.size(); \n    int ans = 0;\n    vector nets(n);\n    for (int s = 0; s < 1 << r; ++s) {\n      fill(begin(nets), end(nets), 0);\n      for (int j = 0; j < r; ++j)\n        if (s & (1 << j)) {\n          --nets[requests[j][0]];\n          ++nets[requests[j][1]];\n        }\n      if (all_of(begin(nets), end(nets), [](const int x) { return x == 0; }))\n        ans = max(ans, __builtin_popcount(s));\n    }\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def maximumRequests(self, n: int, requests: List[List[int]]) -> int:\n    r = len(requests)\n    ans = 0\n    for s in range(1 << r):\n      degrees = [0] * n\n      for i in range(r):\n        if s & (1 << i):\n          degrees[requests[i][0]] -= 1\n          degrees[requests[i][1]] += 1\n      if not any(degrees):\n        ans = max(ans, bin(s).count('1'))\n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    We have n buildings numbered from 0 to n – 1. Each building has a number of employees. It’s transfer season, and some employees want to change the building they…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[122,217,42],"class_list":["post-7429","post","type-post","status-publish","format-standard","hentry","category-searching","tag-combination","tag-hard","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7429","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7429"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7429\/revisions"}],"predecessor-version":[{"id":7433,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7429\/revisions\/7433"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7429"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7429"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7429"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}