Smallest Team With Every Skill

Hard

You are putting together a team for a project. The project needs every skill listed in skills (all names are distinct). There are some candidates: candidates[i] is the list of skills of candidate i. A team works if every skill in skills is held by at least one of its members. Find a working team with as few people as possible and return the indices of its members (0-based) in any order. The input guarantees that a working team exists and that the smallest one is unique.

Example 1

skills=['sql', 'python', 'excel'], candidates=[['sql'], ['python', 'excel'], ['excel']] → [1, 0]

Candidate 0 knows sql, candidate 1 knows python and excel: together they cover all three skills. Nobody has all three alone.

Example 2

skills=['go', 'k8s', 'aws', 'figma'], candidates=[['go', 'k8s'], ['aws'], ['figma'], ['k8s', 'aws', 'figma']] → [3, 0]

Candidate 3 covers k8s, aws and figma, and only candidate 0 knows go. The two of them are enough, and no single person has everything.

Example 3

skills=['ml'], candidates=[[], ['ml']] → [1]

Candidate 0 has none of the needed skills; candidate 1 alone is enough.

Constraints

1 ≤ len(skills) ≤ 16
1 ≤ len(skills[i]) ≤ 16, lowercase English letters and digits only; all strings in skills are distinct
1 ≤ len(candidates) ≤ 60
0 ≤ len(candidates[i]) ≤ 16; a candidate's skills are distinct and all belong to skills
A working team exists, and the smallest working team is unique

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Dynamic Programming Bitmask