1601. Maximum Number of Achievable Transfer Requests

Problem¶

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 reside in.

You are given an array requests where requests[i] = [from_i, to_i] represents an employee’s request to transfer from building from_i to building to_i.

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

Return the maximum number of achievable requests

Constraints:

• 1 <= n <= 20
• 1 <= requests.length <= 16
• requests[i].length == 2
• 0 <= from_i, to_i < n

Solution¶

Read the problem¶

• There is really low number of request and building. So we can try all possible request combination

Evaluating¶

• Using a binary array to keep track of which request are served served = [False] * requests.length , free slot start on each building is [0] * n
• Let say for each request being done, we mark them as True, we then have a combination of 2 ** requests.length <= 2 **16 or 65536 total of possible out come
• With each one, we can then try and find the total of person in each building, is it all equal to 0? Which cost us a total time complexity O(n) <= 20.
• If that true, then is could be possible answer and we can update the current_max.
• Know possible answer current_max, we will only try to check any served where total number of request being served is greater than current_max;

Which mean time complexity is close to O(n* 2**m) = 20*65536

Get it on¶

• A binary representation is good enough for served array. We can use a for loop in range [0 .. 2**16]. Every 1 position in binary number representation mean request at that position is served

Implementation¶

Sane way¶

class Solution:
    def bit_1_pos(self, number):
        for pos, c in enumerate`-1]`:
            if c == '1':
                yield pos

    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        current_max = 0

        for request_served in range(1 << requests.__len__()):
            building = [0] * n
            pos = requests.__len__() - 1
            if request_served.bit_count() <= current_max:
                continue

            for pos in self.bit_1_pos(request_served):
                building[requests[pos][0]] -= 1
                building[requests[pos][1]] += 1

            check = True
            for i in range(n):
                if building[i] != 0:
                    check = False
                    break

            if check:
                current_max = request_served.bit_count()

        return current_max

Leetcode provided¶

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        answer = 0

        for mask in range(1 << requests.__len__()):
            indegree = [0] * n
            pos = requests.__len__() - 1
            bitCount = mask.bit_count()
            if bitCount <= answer:
                continue

            curr = mask
            while curr > 0:
                if curr & 1 == 1:
                    indegree[requests[pos][0]] -= 1
                    indegree[requests[pos][1]] += 1
                curr >>= 1
                pos -= 1
            flag = True
            for i in range(n):
                if indegree[i] != 0:
                    flag = False
                    break

            if flag:
                answer = bitCount
        return answer