Smallest Sufficient Team

Similar Problems:

- CheatSheet: LeetCode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #dynamicprogramming, #bitmaskdp

In a project, you have a list of required skills req_skills, and a list of people. The i-th person people[i] contains a list of skills that person has.

Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person: for example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].

Return any sufficient team of the smallest possible size, represented by the index of each person.

You may return the answer in any order. It is guaranteed an answer exists.

Example 1:

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]] Output: [0,2]

Example 2:

Input: 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
- 1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
- Elements of req_skills and people[i] are (respectively) distinct.
- req_skills[i][j], people[i][j][k] are lowercase English letters.
- Every skill in people[i] is a skill in req_skills.
- It is guaranteed a sufficient team exists.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

## https://code.dennyzhang.com/smallest-sufficient-team ## Basic Ideas: bitmask + dynamic programming ## ## Get a certain set of skill, how many person we would need ## ## dp(skills) -> int ## ## dp(2^n-1) ## ## Complexity: Time ?, Space ? class Solution: def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]: skills = {v:i for i, v in enumerate(req_skills)} dp = {0:[]} for i, l in enumerate(people): thy_skill = 0 for s in l: thy_skill |= 2**skills[s] for cur_skill in list(dp.keys()): workers = dp[cur_skill] with_skill = cur_skill | thy_skill # This worker doesn't help if with_skill == cur_skill: continue if with_skill not in dp or len(dp[with_skill]) > len(workers)+1: dp[with_skill] = workers+[i] return dp[2**len(skills)-1]