Leanest Skill Squad
HardBit Manipulation
Problem
A project needs every skill in required (distinct names). people[p] lists the skills person p has; people may have skills the project does not need.
Return the smallest number of people whose combined skills cover all of required. It is guaranteed that hiring everyone covers them.
Example 1
- Input:
- required = ["sql", "ui", "ops"], people = [["sql"], ["ui"], ["ui", "ops"]]
- Output:
- 2
People 0 and 2 cover sql, ui and ops.
Example 2
- Input:
- required = ["go"], people = [["rust"], ["go", "rust"]]
- Output:
- 1
Constraints
- 1 ≤ required.length ≤ 12
- 1 ≤ people.length ≤ 60
- 0 ≤ people[p].length ≤ 12
- Skill names are non-empty lowercase strings.
Hint
Show the first hint
Greedy 'pick whoever covers the most missing skills' is not optimal. With at most 12 skills, what can you enumerate?
Walkthrough
How to approach it
01Clarify before coding
- Do extra skills matter? No, only required skills count, so they are dropped from the masks.
- Is a solution guaranteed? Yes, everyone together covers all required skills.
- Return the people or only the count? Only the count, which is unique even when several teams tie.
02Brute force
Try teams of size 1, 2, 3, … over all combinations of people and stop at the first size that covers everything.
Cost: Up to C(60, k) teams per size: with an answer of 6, C(60, 6) ≈ 5 · 10^7 teams. Explodes quickly.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.