catalogue

1. Title Description

2. Problem solving analysis

3. Code implementation

1. Title Description

We have n buildings, numbered from 0 to n - 1. There are several employees in each building. As it is the season to change buildings, some employees want to live in another building.
Give you an array of requests, where requests[i] = [fromi, toi], indicating that an employee requests to move from the building numbered fromi to the building numbered toi. At the beginning, all buildings are full, so several requests selected from the request list are feasible, and the net change of employees in each building needs to be 0. It means that the number of employees leaving each building is equal to the number of employees moving in.
For example, if n = 3 and two employees want to leave building 0, one employee wants to leave building 1 and one employee wants to leave building 2, if the request list is feasible, two employees should move into building 0, one employee into building 1 and one employee into building 2.
Please select several requests from the original request list, make them a feasible request list, and return the maximum number of requests in all feasible lists.

Example 1:
 

Input: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
Output: 5
Explanation: the request list is as follows:
The employees leaving building 0 are x and y, and they all want to move to building 1.
The employees leaving Building 1 are a and b, and they want to move to building 2 and 0, respectively.
The employee leaving Building 2 is z and he wants to move to building 0.
The employee leaving building 3 is c and he wants to move to building 4.
No staff left building 4.
We can let x and b exchange their buildings to meet their request.
We can let y, a and z exchange positions between the three buildings to meet their requirements.
Therefore, up to 5 requests can be satisfied.

Example 2:

Input: n = 3, requests = [[0,0],[1,2],[2,1]]
Output: 3
Explanation: the request list is as follows:
The employee leaving building 0 is x, and he wants to return to the original building 0.
The employee leaving Building 1 is y and he wants to move to building 2.
The employee leaving Building 2 is z and he wants to move to building 1.
We can meet all requests.

Example 3:
Input: n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
Output: 4
 
Tips:
1 <= n <= 20
1 <= requests.length <= 16
requests[i].length == 2
0 <= fromi, toi < n

Source: LeetCode
Link: https://leetcode-cn.com/problems/maximum-number-of-achievable-transfer-requests
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

2. Problem solving analysis

Find the largest subset, in which all requests can be satisfied.

Obviously, it is a necessary condition that the net access of the houses involved in all requests in the subset must be 0. The question is whether this is a sufficient condition?

It can be proved that this is indeed a sufficient condition. The following is proved by constructive method:

Suppose that group k requests are recorded as [x1, Y1], [X2, Y2], [xk,yk].

First look at [x1,y1]. Since the net inflow and outflow of each house is 0, there must be at least one xi=y1(i!=1) in other requests. Similarly, there must be at least one yj=x1(i!=1)  

        . . . It seems that it is not as easy to explain as the first sense imagined, to be added.

       

Thus, a violent search solution can be obtained:

From large to small, evaluate each possible subset to see whether the net inflow and outflow of each house is 0.

3. Code implementation

import sys
import time
import random
import collections
import itertools as it
from   typing import List

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        def judge(requests):
            d = n*[0]
            for req in requests:
                d[req[0]] -= 1
                d[req[1]] += 1                
            return min(d)==0 and max(d)==0
        
        for k in range(len(requests),0,-1):
            # print(k)
            for reqs in it.combinations(requests, k):        
                # print(reqs)
                if judge(reqs):
                    return k
        return 0

if __name__ == '__main__':        
            
    sln = Solution()

    # n    = 1
    # reqs = [[0,0]]
    # tStart = time.time()        
    # print('reqs=',reqs,' ans=', sln.maximumRequests(n,reqs))
    # tElapsed = time.time() - tStart        
    # print('tElapsed = ', tElapsed, ' (sec)')   

    n = 3
    reqs = [[1,2],[1,2],[2,2],[0,2],[2,1],[1,1],[1,2]]
    tStart = time.time()        
    print('reqs=',reqs,' ans=', sln.maximumRequests(n,reqs))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')   
    
    n    = 5
    reqs = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
    tStart = time.time()        
    print('reqs=',reqs,' ans=', sln.maximumRequests(n,reqs))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')   

    n    = 3
    reqs = [[0,0],[1,2],[2,1]]
    tStart = time.time()        
    print('reqs=',reqs,' ans=', sln.maximumRequests(n,reqs))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')       
    
    n    = 4
    reqs = [[0,3],[3,1],[1,2],[2,0]]
    tStart = time.time()        
    print('reqs=',reqs,' ans=', sln.maximumRequests(n,reqs))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')     
    
    n    = 20
    reqs = []
    for k in range(16):
        tmp = [random.randint(0,n-1),random.randint(0,n-1)]
        reqs.append(tmp)
    tStart = time.time()        
    print('reqs=',reqs,' ans=', sln.maximumRequests(n,reqs))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')   

General catalogue of this series: Leetcode problem solving notes of slow ploughing of stupid cattle (dynamic update...)https://chenxiaoyuan.blog.csdn.net/article/details/123040889