In a project, you have a list of required skills req_skills, and a list of people. The ith person people[i] contains a list of skills that the person has.
Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.
For example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].
Return any sufficient team of the smallest possible size, represented by the index of each person. You may return the answer in any order.
The key idea is to represent each skill as a bit in an integer, and use dynamic programming to keep track of the smallest team for each possible combination of skills. By iterating through people and updating the DP table, we can efficiently find the smallest sufficient team.
classSolution {
publicint[]smallestSufficientTeam(List<String> req_skills, List<List<String>> people) {
int n = req_skills.size();
Map<String, Integer> skillIdx =new HashMap<>();
for (int i = 0; i < n; ++i) skillIdx.put(req_skills.get(i), i);
int[] pMask =newint[people.size()];
for (int i = 0; i < people.size(); ++i) {
for (String s : people.get(i)) pMask[i]|= 1 << skillIdx.get(s);
}
Map<Integer, List<Integer>> dp =new HashMap<>();
dp.put(0, new ArrayList<>());
for (int i = 0; i < pMask.length; ++i) {
Map<Integer, List<Integer>> dpCopy =new HashMap<>(dp);
for (Map.Entry<Integer, List<Integer>> entry : dpCopy.entrySet()) {
int newMask = entry.getKey() | pMask[i];
List<Integer> team =new ArrayList<>(entry.getValue());
team.add(i);
if (!dp.containsKey(newMask) || dp.get(newMask).size() > team.size()) {
dp.put(newMask, team);
}
}
}
List<Integer> ans = dp.get((1 << n) - 1);
return ans.stream().mapToInt(i -> i).toArray();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
funsmallestSufficientTeam(reqSkills: List<String>, people: List<List<String>>): IntArray {
val n = reqSkills.size
val skillIdx = reqSkills.withIndex().associate { it.value to it.index }
val pMask = people.map { p -> p.fold(0) { acc, s -> acc or (1 shl skillIdx[s]!!) } }
val dp = mutableMapOf(0 to listOf<Int>())
for (i in pMask.indices) {
val dpCopy = dp.toMap()
for ((mask, team) in dpCopy) {
val newMask = mask or pMask[i]
if (newMask !in dp || dp[newMask]!!.size > team.size + 1) {
dp[newMask] = team + i
}
}
}
return dp[(1 shl n) - 1]!!.toIntArray()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
defsmallestSufficientTeam(req_skills: list[str], people: list[list[str]]) -> list[int]:
n = len(req_skills)
skill_idx = {s: i for i, s in enumerate(req_skills)}
p_mask = [(sum(1<< skill_idx[s] for s in p)) for p in people]
dp: dict[int, list[int]] = {0: []}
for i, mask in enumerate(p_mask):
dp_copy = dp.copy()
for m, team in dp_copy.items():
new_mask = m | mask
if new_mask notin dp or len(dp[new_mask]) > len(team) +1:
dp[new_mask] = team + [i]
return dp[(1<< n) -1]