Problem description

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]

Solution

This problem is a set cover problem. Set Cover Problem

This problem is proved to be NP-Complete. To solve this we need to encode the skills using bits. Let’s say a sub set of required skills is skill_set = [a, b, c, d], then DP[skill_set] can be constructed for all the subsets of req_skills. There are 2ⁿ numbers of sub sets of req_skills. So, the solution will take O(2ⁿ) space, where n is total number of skills in req_skills set.

To ammend each skill_set to be req_skills, there are at most m steps (each step add a person), where m is the total number of person.

Here we can implement a Bell-Ford like procedure to calculate DP[skill_set]. DP[skill_set] will converge in m steps.

Below is my python implementation

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skill2idx = {skill : idx for idx, skill in enumerate(req_skills)}
        n = len(req_skills)
        dp = {0: []}
        for i, person in enumerate(people):
            his_skill = 0
            for skill in person:
                his_skill |= (1 << skill2idx[skill]) 
            for skills, pset in list(dp.items()):
                with_him = skills | his_skill
                if skills == with_him:
                    continue
                if with_him not in dp.keys() or len(pset) + 1 < len(dp[with_him]):
                    dp[with_him] = pset + [i]
        return dp[(1 << n) - 1]