{x}
blog image

Smallest Sufficient Team

In a project, you have a list of required skills req_skills, and a list of people. The ith person people[i] contains a list of skills that the 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 <= req_skills[i].length <= 16
  • req_skills[i] consists of lowercase English letters.
  • All the strings of req_skills are unique.
  • 1 <= people.length <= 60
  • 0 <= people[i].length <= 16
  • 1 <= people[i][j].length <= 16
  • people[i][j] consists of lowercase English letters.
  • All the strings of people[i] are unique.
  • Every skill in people[i] is a skill in req_skills.
  • It is guaranteed a sufficient team exists.

Solution Explanation: Smallest Sufficient Team

This problem asks to find the smallest team of people who collectively possess all the required skills. The solution utilizes state compression dynamic programming and bit manipulation for efficiency.

Core Idea:

We represent the skills as bits in an integer. Each bit corresponds to a skill; if the bit is set (1), the skill is present; otherwise, it's not (0). This allows us to represent combinations of skills compactly. We use dynamic programming to find the minimum number of people needed to achieve each possible skill combination.

Algorithm:

  1. Skill Mapping: Create a dictionary (or map) to map each skill name to a unique bit position (integer).

  2. People Encoding: For each person, create an integer representing their skills. If a person possesses skill i, the i-th bit in the integer will be set (using bitwise OR).

  3. Dynamic Programming (DP):

    • dp[mask] : Stores the minimum number of people needed to achieve the skill combination represented by the binary mask. Initialize all entries to infinity, except dp[0] = 0 (no people needed for no skills).

    • Iterate through all possible skill combinations (masks):

      • Iterate through each person:
        • If adding the person's skills (person_skills) to the current combination (mask) results in a new combination (new_mask = mask | person_skills), and if dp[mask] + 1 < dp[new_mask] (meaning we found a better way to achieve new_mask), update dp[new_mask] to dp[mask] + 1.

  4. Backtracking: Once the DP table is complete, dp[(1 << m) - 1] (where m is the number of skills) contains the minimum team size. We reconstruct the team by backtracking through the DP table, starting from this final state and following the path that led to it.

Time Complexity: O(2m * n), where m is the number of skills and n is the number of people. The outer loop iterates through all possible skill combinations (2m), and the inner loop iterates through people (n).

Space Complexity: O(2m) to store the DP table.

Code Examples:

The code examples in Python, Java, C++, Go and TypeScript provided in the previous response clearly implement this algorithm. The inf variable represents infinity (a large value) to indicate unreachable skill combinations initially. The code efficiently uses bitwise operations for speed. The backtracking step is crucial for reconstructing the team members.

Example Walkthrough (Python):

Let's consider the example: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]].

  1. Skill Mapping: {"java": 0, "nodejs": 1, "reactjs": 2}

  2. People Encoding: p = [1, 2, 6] (binary: 001, 010, 110)

  3. DP: The DP table will be built iteratively. For instance, reaching the state 7 (binary 111, representing all skills) might be achieved by combining person 0 (java) and person 2 (nodejs, reactjs), resulting in a team size of 2.

  4. Backtracking: After computing dp, we start from the state 7 and trace back to find the people who were used to reach this state.

The provided codes implement this algorithm, achieving a concise and efficient solution for the "Smallest Sufficient Team" problem.