Sponsored
Sponsored
This approach leverages a bitmask along with dynamic programming to solve the problem of finding the smallest sufficient team. We use a bitmask to represent the combination of skills possessed by a team. Dynamic programming is employed to track the smallest team for every possible combination of skills, allowing us to build up to a team that covers all required skills.
Time Complexity: O(people.length * 2^n), where n is the number of required skills. Space Complexity: O(2^n).
1#include <vector>
2#include <string>
3#include <unordered_map>
4
5using namespace std;
6
7vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
8 int n = req_skills.size();
9 unordered_map<string, int> skill_index;
10 for (int i = 0; i < n; ++i) {
11 skill_index[req_skills[i]] = i;
12 }
13 vector<int> dp(1 << n, INT_MAX);
14 vector<vector<int>> team(1 << n);
15 dp[0] = 0;
16
17 for (int i = 0; i < people.size(); ++i) {
18 int his_skill = 0;
19 for (const string& skill : people[i]) {
20 if (skill_index.count(skill)) {
21 his_skill |= 1 << skill_index[skill];
22 }
23 }
24 for (int mask = 0; mask < (1 << n); ++mask) {
25 int new_mask = mask | his_skill;
26 if (dp[new_mask] > dp[mask] + 1) {
27 dp[new_mask] = dp[mask] + 1;
28 team[new_mask] = team[mask];
29 team[new_mask].push_back(i);
30 }
31 }
32 }
33
34 return team[(1 << n) - 1];
35}In this C++ implementation, we use a vector dp to keep track of the smallest size of a team needed to cover each set of skills, represented by a bitmask, similar to the Python implementation.
The vector team records the index of members for each skill set. We iterate over each person and compute their skills bitmask. We then iterate over all combinations of existing skills in dp using bitmask operations to see if including this person can form a new, smaller team for any skill set.
This approach utilizes backtracking to explore all possible combinations of people in attempting to form the smallest team covering all required skills. We prune branches once we find a valid team, retaining the best (smallest) solution observed so far.
Time Complexity: O(2^people.length), worst case exploring all combinations. Space Complexity: O(people.length) due to recursive depth.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 int minSize = int.MaxValue;
6 List<int> bestTeam = new List<int>();
public int[] SmallestSufficientTeam(string[] req_skills, IList<IList<string>> people) {
var skillIndex = new Dictionary<string, int>();
for (int i = 0; i < req_skills.Length; ++i) {
skillIndex[req_skills[i]] = i;
}
int[] peopleSkills = new int[people.Count];
for (int i = 0; i < people.Count; ++i) {
foreach (var skill in people[i]) {
if (skillIndex.ContainsKey(skill))
peopleSkills[i] |= 1 << skillIndex[skill];
}
}
Backtrack(peopleSkills, 0, new List<int>(), 0, (1 << req_skills.Length) - 1);
return bestTeam.ToArray();
}
private void Backtrack(int[] peopleSkills, int index, List<int> currentTeam, int currentSkills, int fullSkills) {
if (currentSkills == fullSkills) {
if (currentTeam.Count < minSize) {
minSize = currentTeam.Count;
bestTeam = new List<int>(currentTeam);
}
return;
}
if (index == peopleSkills.Length || currentTeam.Count >= minSize) {
return;
}
Backtrack(peopleSkills, index + 1, currentTeam, currentSkills, fullSkills);
currentTeam.Add(index);
Backtrack(peopleSkills, index + 1, currentTeam, currentSkills | peopleSkills[index], fullSkills);
currentTeam.RemoveAt(currentTeam.Count - 1);
}
}The C# solution uses a similar backtracking method. It computes the state by converting skills into a bitmask and recurses by selectively adding people to the team. When a complete team is found that covers all required skills, it checks if it's the smallest seen so far. Branches are pruned if they're suboptimal by current measurement.