aboutsummaryrefslogtreecommitdiff
path: root/smallest_sufficient_team.cpp
blob: 473e21829e2a12abc0d5a2643aa25a929051fd7c (plain)
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 1125. Smallest Sufficient Team
#include "leetcode.h"

/*
 * in a project, you have a list of required required skills ' req_skills' and a
 * list of people. the i'th person 'people[i]' contains a list of skills that
 * the 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
 * tema who has that skill. we can represent these teams by the index of each
 * person. 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
 */

class Solution {
public:
  vector<int> smallestSufficientTeam(vector<string> &req_skills,
                                     vvd(string) & people) {
    int n = req_skills.size();
    unordered_map<int, vector<int>> ans;
    ans.reserve(1 << n);
    ans[0] = {};
    unordered_map<string, int> skill_map;
    for (int i = 0; i < n; i++)
      skill_map[req_skills[i]] = i;
    for (int i = 0; i < people.size(); i++) {
      int curr = 0;
      for (int j = 0; j < people[i].size(); j++)
        curr |= 1 << skill_map[people[i][j]];
      for (auto k = ans.begin(); k != ans.end(); k++) {
        int com = k->first | curr;
        if (ans.find(com) == ans.end() ||
            ans[com].size() > 1 + ans[k->first].size()) {
          ans[com] = k->second;
          ans[com].push_back(i);
        }
      }
    }
    return ans[(1 << n) - 1];
  }
};

int main() {
  Solution obj;
  vector<string> rs1 = {"java", "nodejs", "reactjs"};
  vvd(string) p1 = {{"java"}, {"nodejs"}, {"nodejs", "reactjs"}};
  vector<string> rs2 = {"algorithms", "math",   "java",
                        "reactjs",    "csharp", "aws"};
  vvd(string) p2 = {{"algorithms", "math", "java"},
                    {"algorithms", "math", "reactjs"},
                    {"java", "csharp", "aws"},
                    {"reactjs", "csharp"},
                    {"csharp", "math"},
                    {"aws", "java"}};
  for (auto i : obj.smallestSufficientTeam(rs1, p1))
    printf("%d ", i); // expect: 0 2
  printf("\n");
  for (auto i : obj.smallestSufficientTeam(rs2, p2))
    printf("%d ", i); // expect: 1 2
  printf("\n");
}