Smallest Team Covering All Required Skills
You have a list of required skills and a pool of people, each with some subset of those skills. Assemble the smallest team whose combined skills cover every requirement.
Problem
Given an array req_skills of distinct required skills and an array people where people[i] is the list of skills person i has, return the indices of any smallest team (sufficient team) such that the union of the team's skills equals all of req_skills. Any valid minimum-size team is accepted.
Input
An array req_skills of skill names and an array people of skill-name lists.
Output
An array of person indices forming a smallest sufficient team.
Constraints
- 1 <= req_skills.length <= 16
- 1 <= people.length <= 60
- A sufficient team is guaranteed to exist.
Examples
Example 1
Input
req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output
[0,2]
Person 0 covers java; person 2 covers nodejs+reactjs.
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]
Persons 1 and 2 together cover all six skills.