Match users with other teams

题目是：

You are given a list of users with name and team they belong to. Now you have to match every user to one other user randomly so that they can get to know each other. User match should be from different team. Find out the maximum possible match. If list size is odd then you can ignore one user.

Example - Input - [["Alex","Infra"],["Kevin","Search"],["Jill","HR"],["Jane","Infra"],["Justin","Search"],["Michael","HR"]]

Output - [["Alex","Justin"],["Kevin","Jill"],["Jane","Michael"]]

We dont want  ["Alex","Justin"] and ["Jane","Kevin"] combination. In that case we will left with 2 members from team HR so we are wasting 2 members here.

按组放进dictionary，然后用max heap排序，每次抽取前两个组match，把剩下的放回heap，但总是会漏到一些case。

大神能给个提示吗


补充内容 (2021-08-29 10:27 +8:00):
做出来了：

思路还是是按组放进dictionary，然后用max heap排序，每次抽取前两个组match(之前是尽可能最大match数量，现在只match 1 组)，把剩下的放回heap。

请问大神们有建议吗？

python , 大神指点下：
···

1. 
   
2. <div class="blockcode"><blockquote>def match_team(members):
   
3.     hq = []
   
4.     team_members = collections.defaultdict(list)
   
5.     for mem, team in members:
   
6.         team_members[team].append(mem)
   
7.     for team, members in team_members.items():
   
8.         heapq.heappush(hq, (-len(members), team, members))
   
9.     res = []
   
10.     while len(hq) >= 2:
    
11.         print(hq)
    
12.         a_len, a_team, a_members = heapq.heappop(hq)
    
13.         b_len, b_team, b_members = heapq.heappop(hq)
    
14.         res.append((a_members.pop(), b_members.pop()))
    
15.         if a_len < -1:
    
16.             heapq.heappush(hq, (a_len+1, a_team, a_members))
    
17.         if b_len < -1:
    
18.             heapq.heappush(hq, (b_len+1, b_team, b_members))
    
19.     return res
    
20. 
    
21. input = [["Alex","Infra"],["Kevin","Search"],["Jill","HR"],["Jane","Infra"],["Justin","Search"],["Michael","HR"]]
    
22. print(match_team(input))

复制代码