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
andpeople[i]
are (respectively) distinct. req_skills[i][j], people[i][j][k]
are lowercase English letters.- It is guaranteed a sufficient team exists.
Solution: DP
C++/Array
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 |
// Author: Huahua, 24 ms / 11 MB class Solution { public: vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) { const int n = req_skills.size(); const int target = (1 << n) - 1; vector<int> skills; for (const auto& p : people) { int mask = 0; for (const string& s: p) mask |= (1 << find(begin(req_skills), end(req_skills), s) - begin(req_skills)); skills.push_back(mask); } vector<int> dp((1 << n), INT_MAX / 2); vector<pair<int, int>> pt((1 << n)); dp[0] = 0; for (int i = 0; i < people.size(); ++i) { const int k = skills[i]; if (k == 0) continue; for (int j = target; j >= 0; --j) if (dp[j] + 1 < dp[j | k]) { dp[j | k] = dp[j] + 1; pt[j | k] = {j, i}; } } int t = target; vector<int> ans; while (t) { ans.push_back(pt[t].second); t = pt[t].first; } return ans; } }; |
C++/HashTable
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 |
// Author: Huahua, 272 ms / 94.8 MB class Solution { public: vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) { const int n = req_skills.size(); vector<int> skills; for (const auto& p : people) { int mask = 0; for (const string& s: p) mask |= (1 << find(begin(req_skills), end(req_skills), s) - begin(req_skills)); skills.push_back(mask); } unordered_map<int, vector<int>> dp; dp[0] = {}; for (int i = 0; i < people.size(); ++i) { unordered_map<int, vector<int>> tmp(dp); for (const auto& kv : dp) { int k = kv.first | skills[i]; if (!tmp.count(k) || kv.second.size() + 1 < tmp[k].size()) { tmp[k] = kv.second; tmp[k].push_back(i); } } tmp.swap(dp); } return dp[(1 << n) - 1]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment