-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLC0040.py
33 lines (32 loc) · 1.23 KB
/
LC0040.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
def smallestSufficientTeam(self, req_skills: List[str],
people: List[List[str]]) -> List[int]:
n = len(people)
m = len(req_skills)
skill_id = dict()
for i, skill in enumerate(req_skills):
skill_id[skill] = i
skills_mask_of_person = [0] * n
for i in range(n):
for skill in people[i]:
skills_mask_of_person[i] |= 1 << skill_id[skill]
dp = [-1] * (1 << m)
dp[0] = 0
def f(skills_mask):
if dp[skills_mask] != -1:
return dp[skills_mask]
for i in range(n):
new_skills_mask = skills_mask & ~skills_mask_of_person[i]
if new_skills_mask != skills_mask:
people_mask = f(new_skills_mask) | (1 << i)
if (dp[skills_mask] == -1 or
people_mask.bit_count()
< dp[skills_mask].bit_count()):
dp[skills_mask] = people_mask
return dp[skills_mask]
answer_mask = f((1 << m) - 1)
ans = []
for i in range(n):
if (answer_mask >> i) & 1:
ans.append(i)
return ans