In a project, you have a list of required skills
req_skills
, and a list of
people
. The i-th person
people[i]
contains a list of skills that 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.
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 <= 16
-
1 <= people.length <= 60
-
1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
-
Elements of
req_skills
and
people[i]
are (respectively) distinct. -
req_skills[i][j], people[i][j][k]
are lowercase English letters. -
Every skill in
people[i]
is a skill in
req_skills
. - It is guaranteed a sufficient team exists.
解题思路：
这道题跟
leetcode 691 stickers to spell word
很类似 ， 可以用BFS来做，将每个人符合技能要求中的技能都加进去。
这里需要做一些优化，不然会超时 ；
//当p[i]没有r_skills中出现的第一个技能的时候，就直接跳出。思路也跟691的优化思路是一致的 ；
else if(cnt == 0 && !p[i].count(ele))
{
break ;
}class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people)
{
if(req_skills.empty()) return {} ;
unordered_set<string> rs ;
unordered_set<int> visited ;
vector<unordered_set<string>> p(people.size()) ;
for(int i = 0 ; i < req_skills.size() ; ++i) rs.insert(req_skills[i]) ;
for(int i = 0 ; i < people.size() ; i++)
for(int j = 0 ; j < people[i].size() ; ++j)
p[i].insert(people[i][j]) ;
queue<pair<unordered_set<string> , unordered_set<int>>> q ;
q.push({rs , visited}) ;
vector<int> res ;
while(!q.empty())
{
for(int sz = q.size() ; sz > 0 ; --sz)
{
unordered_set<string> r_skills = q.front().first ;
unordered_set<int> v = q.front().second ;
q.pop() ;
if(r_skills.empty())
{
for(auto ele : v)
{
res.push_back(ele) ;
}
return res ;
}
for(int i = 0 ; i < people.size() ; ++i)
{
if((!v.empty() && v.count(i)) || p[i].empty()) continue ;
unordered_set<string> tmp = r_skills ;
unordered_set<int> vtmp = v ;
int cnt = 0 ;
for(auto ele : r_skills)
{
if(p[i].count(ele))
{
cnt++ ;
tmp.erase(ele) ;
}
else if(cnt == 0 && !p[i].count(ele))
{
break ;
}
}
if(cnt)
{
vtmp.insert(i) ;
if(tmp.empty())
{
for(auto ele : vtmp)
{
res.push_back(ele) ;
}
return res ;
}
q.push({tmp , vtmp}) ;
}
}
}
}
return {} ;
}
};