Hard

Smallest Sufficient Team

LAB

Given required skills and people skill indices, return the smallest lexicographic team of people covering all skills.

EXAMPLES

Example 1

Input
{
  "reqSkills": [
    "java",
    "nodejs",
    "reactjs"
  ],
  "people": [
    [
      0
    ],
    [
      1
    ],
    [
      1,
      2
    ]
  ]
}

Output
[
  0,
  2
]

FUNCTION SHAPE

reqSkills: stringArraypeople: intMatrix→intArray

SOLUTION NOTE

Bitmask represents which skills are covered. For each state, try adding each person and take the smallest team.

Reveal reference solution +

pythonREFERENCE

def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
    skill_idx = {s: i for i, s in enumerate(req_skills)}
    n = len(req_skills)
    ALL = (1 << n) - 1

    # Convert each person's skills to bitmask
    person_masks = []
    for person in people:
        mask = 0
        for skill in person:
            if skill in skill_idx:
                mask |= (1 << skill_idx[skill])
        person_masks.append(mask)

    @cache
    def dp(mask):
        if mask == ALL: return []
        res = None
        for i, pmask in enumerate(person_masks):
            if pmask & ~mask:  # Person has skills we need
                team = dp(mask | pmask)
                if res is None or len(team) + 1 < len(res):
                    res = [i] + team
        return res if res else list(range(len(people)))  # Fallback

    return dp(0)

TimeO(people × 2^skills)

SpaceO(2^skills)

Open on LeetCode ↗