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).
1def smallest_sufficient_team(req_skills, people):
2 skill_index = {skill: i for i, skill in enumerate(req_skills)}
3 n = len(req_skills)
4 dp = {0: []}
5
6 for i, p in enumerate(people):
7 his_skill = 0
8 for skill in p:
9 if skill in skill_index:
10 his_skill |= 1 << skill_index[skill]
11 new_dp = dp.copy()
12 for skill_set, team in dp.items():
13 with_him = skill_set | his_skill
14 if with_him == skill_set:
15 continue
16 if with_him not in new_dp or len(new_dp[with_him]) > len(team) + 1:
17 new_dp[with_him] = team + [i]
18 dp = new_dp
19
20 return dp[(1 << n) - 1]The code utilizes a dictionary, skill_index, to map each skill to a unique index. We then define a dynamic programming dictionary, dp, where each key represents a set of skills (using bitmask), and value is the team of indices representing people with these skills.
For each person, we calculate the his_skill bitmask, which marks the skills this person can cover. We iterate over each entry in our dynamic programming table, updating it with the new combinations of skills that could be formed by adding the current person.
The result is found in dp[(1 << n) - 1], where n is the length of req_skills, representing the full set of skills covered.
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.