leetcode

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 };