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 skillspeople[0],people[1], andpeople[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 <= 161 <= req_skills[i].length <= 16req_skills[i]consists of lowercase English letters.- All the strings of
req_skillsare unique. 1 <= people.length <= 600 <= people[i].length <= 161 <= people[i][j].length <= 16people[i][j]consists of lowercase English letters.- All the strings of
people[i]are unique. - Every skill in
people[i]is a skill inreq_skills. - It is guaranteed a sufficient team exists.
class Solution:
def smallestSufficientTeam(
self, req_skills: List[str], people: List[List[str]]
) -> List[int]:
d = {s: i for i, s in enumerate(req_skills)}
m, n = len(req_skills), len(people)
p = [0] * n
for i, ss in enumerate(people):
for s in ss:
p[i] |= 1 << d[s]
f = [inf] * (1 << m)
g = [0] * (1 << m)
h = [0] * (1 << m)
f[0] = 0
for i in range(1 << m):
if f[i] == inf:
continue
for j in range(n):
if f[i] + 1 < f[i | p[j]]:
f[i | p[j]] = f[i] + 1
g[i | p[j]] = j
h[i | p[j]] = i
i = (1 << m) - 1
ans = []
while i:
ans.append(g[i])
i = h[i]
return ansclass Solution {
public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
Map<String, Integer> d = new HashMap<>();
int m = req_skills.length;
int n = people.size();
for (int i = 0; i < m; ++i) {
d.put(req_skills[i], i);
}
int[] p = new int[n];
for (int i = 0; i < n; ++i) {
for (var s : people.get(i)) {
p[i] |= 1 << d.get(s);
}
}
int[] f = new int[1 << m];
int[] g = new int[1 << m];
int[] h = new int[1 << m];
final int inf = 1 << 30;
Arrays.fill(f, inf);
f[0] = 0;
for (int i = 0; i < 1 << m; ++i) {
if (f[i] == inf) {
continue;
}
for (int j = 0; j < n; ++j) {
if (f[i] + 1 < f[i | p[j]]) {
f[i | p[j]] = f[i] + 1;
g[i | p[j]] = j;
h[i | p[j]] = i;
}
}
}
List<Integer> ans = new ArrayList<>();
for (int i = (1 << m) - 1; i != 0; i = h[i]) {
ans.add(g[i]);
}
return ans.stream().mapToInt(Integer::intValue).toArray();
}
}class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
unordered_map<string, int> d;
int m = req_skills.size(), n = people.size();
for (int i = 0; i < m; ++i) {
d[req_skills[i]] = i;
}
int p[n];
memset(p, 0, sizeof(p));
for (int i = 0; i < n; ++i) {
for (auto& s : people[i]) {
p[i] |= 1 << d[s];
}
}
int f[1 << m];
int g[1 << m];
int h[1 << m];
memset(f, 63, sizeof(f));
f[0] = 0;
for (int i = 0; i < 1 << m; ++i) {
if (f[i] == 0x3f3f3f3f) {
continue;
}
for (int j = 0; j < n; ++j) {
if (f[i] + 1 < f[i | p[j]]) {
f[i | p[j]] = f[i] + 1;
g[i | p[j]] = j;
h[i | p[j]] = i;
}
}
}
vector<int> ans;
for (int i = (1 << m) - 1; i; i = h[i]) {
ans.push_back(g[i]);
}
return ans;
}
};func smallestSufficientTeam(req_skills []string, people [][]string) (ans []int) {
d := map[string]int{}
for i, s := range req_skills {
d[s] = i
}
m, n := len(req_skills), len(people)
p := make([]int, n)
for i, ss := range people {
for _, s := range ss {
p[i] |= 1 << d[s]
}
}
const inf = 1 << 30
f := make([]int, 1<<m)
g := make([]int, 1<<m)
h := make([]int, 1<<m)
for i := range f {
f[i] = inf
}
f[0] = 0
for i := range f {
if f[i] == inf {
continue
}
for j := 0; j < n; j++ {
if f[i]+1 < f[i|p[j]] {
f[i|p[j]] = f[i] + 1
g[i|p[j]] = j
h[i|p[j]] = i
}
}
}
for i := 1<<m - 1; i != 0; i = h[i] {
ans = append(ans, g[i])
}
return
}function smallestSufficientTeam(req_skills: string[], people: string[][]): number[] {
const d: Map<string, number> = new Map();
const m = req_skills.length;
const n = people.length;
for (let i = 0; i < m; ++i) {
d.set(req_skills[i], i);
}
const p: number[] = new Array(n).fill(0);
for (let i = 0; i < n; ++i) {
for (const s of people[i]) {
p[i] |= 1 << d.get(s)!;
}
}
const inf = 1 << 30;
const f: number[] = new Array(1 << m).fill(inf);
const g: number[] = new Array(1 << m).fill(0);
const h: number[] = new Array(1 << m).fill(0);
f[0] = 0;
for (let i = 0; i < 1 << m; ++i) {
if (f[i] === inf) {
continue;
}
for (let j = 0; j < n; ++j) {
if (f[i] + 1 < f[i | p[j]]) {
f[i | p[j]] = f[i] + 1;
g[i | p[j]] = j;
h[i | p[j]] = i;
}
}
}
const ans: number[] = [];
for (let i = (1 << m) - 1; i; i = h[i]) {
ans.push(g[i]);
}
return ans;
}