leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1125.cpp (1118B)

0 class Solution { 1 public: 2 vector<int> smallestSufficientTeam(vector<string> &req_skills, vector<vector<string>> &people) { 3 int n = people.size(), m = req_skills.size(); 4 unordered_map<string, int> index; 5 for (int i = 0; i < m; i++) 6 index[req_skills[i]] = i; 7 vector<int> masks(n); 8 for (int i = 0; i < n; i++) { 9 for (string skill : people[i]) 10 masks[i] |= 1 << index[skill]; 11 } 12 13 vector<long long> dp(1 << m, (1LL << n) - 1); 14 dp[0] = 0; 15 for (int mask = 1; mask < (1 << m); mask++) { 16 for (int i = 0; i < n; i++) { 17 int smask = mask & ~masks[i]; 18 if (smask == mask) continue; 19 long long pmask = dp[smask] | (1LL << i); 20 if (__builtin_popcountll(pmask) < __builtin_popcountll(dp[mask])) dp[mask] = pmask; 21 } 22 } 23 24 long long answerMask = dp[(1 << m) - 1]; 25 vector<int> res; 26 for (int i = 0; i < n; i++) { 27 if ((answerMask >> i) & 1) res.push_back(i); 28 } 29 return res; 30 } 31 };