[LeetCode] Smallest Sufficient Team

1125. Smallest Sufficient Team

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 skills people[0], people[1], and people[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.

  • dp solution
  • Time : O(p^2)
  • Space : O(2^skill)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
unordered_map<string, int> skills;
unordered_map<int, vector<int>> dp;
int skillId = 0;
for(auto req : req_skills) {
skills[req] = skillId++;
}
dp.reserve(1<<skillId);

for(int i = 0; i < people.size(); i++) {
int m = 0;
for(auto skill : people[i]) {
if(skills.count(skill)) {
m |= (1<<skills[skill]);
}
}
if(m == 0) continue;
dp[m] = {i};
for(auto [mask, p] : dp) {
int comb = mask | m;

if(!dp.count(comb) or dp[comb].size() > p.size() + 1) {
dp[comb] = p;
dp[comb].push_back(i);
}
}
}
return dp[(1<<skillId) - 1];
}
};
  • backTracking solution
  • Time : O(2^p)
  • Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
vector<int> res;
void backTracking(vector<int>& masks, int req, vector<int>& tmp, int i) {
if(req == 0) {
if(res.empty() or tmp.size() < res.size()) {
res = tmp;
}
return;
}
if(i == masks.size() or (!res.empty() and tmp.size() >= res.size())) return;

if(masks[i] & req) {
int nreq = req ^ (masks[i]&req);
tmp.push_back(i);
backTracking(masks, nreq, tmp, i + 1);
tmp.pop_back();
}
backTracking(masks, req, tmp, i + 1);
}
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
unordered_map<string, int> skills;
int skillId = 0;
for(auto req : req_skills) {
skills[req] = skillId++;
}
vector<int> masks;
for(auto peopleSkills : people) {
int mask = 0;
for(auto skill : peopleSkills) {
if(skills.count(skill)) {
mask |= (1<<skills[skill]);
}
}
masks.push_back(mask);
}

int req = (1<<skillId) - 1;
vector<int> tmp;
backTracking(masks, req, tmp, 0);
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/09/PS/LeetCode/smallest-sufficient-team/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.