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).
1function smallestSufficientTeam(req_skills, people) {
2 const skillIndex = req_skills.reduce((acc, skill, i) => (acc[skill] = i, acc), {});
3 const n = req_skills.length;
4 let dp = {0: []};
5
6 people.forEach((p, i) => {
7 let hisSkill = 0;
8 p.forEach(skill => {
9 if (skill in skillIndex) {
10 hisSkill |= 1 << skillIndex[skill];
11 }
12 });
13 const newDp = { ...dp };
14 for (const [skillSet, team] of Object.entries(dp)) {
15 const withHim = skillSet | hisSkill;
16 if (newDp[withHim] === undefined || newDp[withHim].length > team.length + 1) {
17 newDp[withHim] = [...team, i];
18 }
19 }
20 dp = newDp;
21 });
22
23 return dp[(1 << n) - 1];
24}The JavaScript solution employs a similar strategy using an object structure to keep track of the smallest team covering each set of skills, denoted as bitmasks. It iterates over each person, computes the bitmask for their skills, and updates possible combinations of team skills within the dynamic programming object dp.
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.