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.
1import java.util.*;
2
3
This Java implementation uses recursion to explore the assembly of teams in a backtracking manner. We map each skill to a bit index, then convert each person's skills to a bitmask. We recursively decide whether to include each person in the current team, pruning branches that exceed the current smallest team's size or cannot complete the skill set. The smallest sufficient team is stored in bestTeam.