You are given a list of required skills, req_skills
, and a list of people. Each person people[i]
has a list of skills they possess.
A sufficient team is a set of people where for every required skill in req_skills
, at least one person in the team has that skill. You can represent a team by the indices of the people in the team.
For example, if team = [0, 1, 3]
, it represents the people with skills people[0]
, people[1]
, and people[3]
.
Your task is to return any sufficient team of the smallest possible size, represented by the indices of the people in the team. The order of the indices in the result doesn't matter. It is guaranteed that a solution exists.
Example 1:
req_skills = ["java", "nodejs", "reactjs"]
people = [["java"], ["nodejs"], ["nodejs", "reactjs"]]
Output: [0, 2]
Example 2:
req_skills = ["algorithms", "math", "java", "reactjs", "csharp", "aws"]
people = [["algorithms", "math", "java"], ["algorithms", "math", "reactjs"], ["java", "csharp", "aws"], ["reactjs", "csharp"], ["csharp", "math"], ["aws", "java"]]
Output: [1, 2]
Constraints:
1 <= req_skills.length <= 16
1 <= people.length <= 60
req_skills
are unique.req_skills
.How would you approach this problem efficiently?
The most straightforward approach is to generate all possible subsets of people and check if each subset forms a sufficient team. Then, find the smallest such team.
from itertools import combinations
def smallestSufficientTeam_brute_force(req_skills, people):
skill_map = {skill: i for i, skill in enumerate(req_skills)}
n_skills = len(req_skills)
people_masks = []
for person_skills in people:
mask = 0
for skill in person_skills:
mask |= (1 << skill_map[skill])
people_masks.append(mask)
for team_size in range(1, len(people) + 1):
for team in combinations(range(len(people)), team_size):
covered_mask = 0
for person_index in team:
covered_mask |= people_masks[person_index]
if covered_mask == (1 << n_skills) - 1:
return list(team)
return []
We can significantly improve the efficiency by using dynamic programming with bit masking. The idea is to represent the covered skills as a bitmask. Each bit in the mask corresponds to a skill. If the i-th bit is set, it means the i-th skill is covered.
dp[mask]
stores the smallest team required to cover the skills represented by the bitmask mask
.dp
array. If adding the person to the current team results in a smaller team size for a given covered skill set, update the dp
array.def smallestSufficientTeam(req_skills, people):
n = len(req_skills)
skill_id = {s: i for i, s in enumerate(req_skills)}
dp = {0: []}
for i, p in enumerate(people):
skills_mask = 0
for skill in p:
skills_mask |= 1 << skill_id[skill]
for mask, team in list(dp.items()):
new_mask = mask | skills_mask
if new_mask not in dp or len(team) + 1 < len(dp[new_mask]):
dp[new_mask] = team + [i]
return dp[(1 << n) - 1]
dp
array, where N is the number of required skills.req_skills
: If req_skills
is empty, any empty team will be a sufficient team, so return an empty list.people
: If people
is empty and req_skills
is not empty, then there is no sufficient team which violates the constraints. The problem states it is guaranteed a sufficient team exists, so this edge case does not need to be handled.