Skip to content

1125. Smallest Sufficient Team 👍

  • Time: $O(p \cdot 2^n)$, where $p = |\texttt{people}|$ and $n = |\texttt{req_skills}|$
  • Space: $O(2^n)$
 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
class Solution {
 public:
  vector<int> smallestSufficientTeam(vector<string>& req_skills,
                                     vector<vector<string>>& people) {
    const int n = req_skills.size();
    const int nSkills = 1 << n;
    unordered_map<string, int> skillToId;
    // dp[i] := the minimum people's indices to cover skillset of mask i
    unordered_map<int, vector<int>> dp;
    dp.reserve(nSkills);  // Avoid rehash.
    dp[0] = {};

    for (int i = 0; i < n; ++i)
      skillToId[req_skills[i]] = i;

    auto getSkill = [&](const vector<string>& person) {
      int mask = 0;
      for (const string& skill : person)
        if (const auto it = skillToId.find(skill); it != skillToId.cend())
          mask |= 1 << it->second;
      return mask;
    };

    for (int i = 0; i < people.size(); ++i) {
      const int currSkill = getSkill(people[i]);
      for (const auto& [mask, indices] : dp) {
        const int newSkillSet = mask | currSkill;
        if (newSkillSet == mask)  // Adding people[i] doesn't increase skill set
          continue;
        if (!dp.contains(newSkillSet) ||
            dp[newSkillSet].size() > indices.size() + 1) {
          dp[newSkillSet] = indices;
          dp[newSkillSet].push_back(i);
        }
      }
    }

    return dp[nSkills - 1];
  }
};

 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
class Solution {
  public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
    final int n = req_skills.length;
    final int nSkills = 1 << n;
    Map<String, Integer> skillToId = new HashMap();
    // dp[i] := the minimum people's indices to cover skillset of mask i
    List<Integer>[] dp = new List[nSkills];
    dp[0] = new ArrayList<>();

    for (int i = 0; i < req_skills.length; ++i)
      skillToId.put(req_skills[i], i);

    for (int i = 0; i < people.size(); ++i) {
      final int currSkill = getSkill(people.get(i), skillToId);
      for (int j = 0; j < nSkills; ++j) {
        if (dp[j] == null)
          continue;
        final int newSkillSet = currSkill | j;
        if (newSkillSet == j) // Adding people[i] doesn't increase skill set
          continue;
        if (dp[newSkillSet] == null || dp[newSkillSet].size() > dp[j].size() + 1) {
          dp[newSkillSet] = new ArrayList<>(dp[j]);
          dp[newSkillSet].add(i);
        }
      }
    }

    return dp[nSkills - 1].stream().mapToInt(Integer::intValue).toArray();
  }

  private int getSkill(List<String> person, Map<String, Integer> skillToId) {
    int mask = 0;
    for (final String skill : person)
      if (skillToId.containsKey(skill))
        mask |= 1 << skillToId.get(skill);
    return mask;
  }
}