leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1125.cpp (1118B)

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