Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1125.html
1125. Smallest Sufficient Team (Hard)
In a project, you have a list of required skills req_skills, and a list of people. The i-th person people[i] contains a list of skills that 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. It is guaranteed an answer exists.
Example 1:
Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]] Output: [0,2]
Example 2:
Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]] Output: [1,2]
Constraints:
1 <= req_skills.length <= 161 <= people.length <= 601 <= people[i].length, req_skills[i].length, people[i][j].length <= 16- Elements of
req_skillsandpeople[i]are (respectively) distinct. req_skills[i][j], people[i][j][k]are lowercase English letters.- Every skill in
people[i]is a skill inreq_skills. - It is guaranteed a sufficient team exists.
Related Topics:
Dynamic Programming, Bit Manipulation
Solution 1. DP
This looks like a knapsack problem. Let’s try to use DP.
To represent which skills each people have, we can use bitmask. For example, 0110 means that this people have 1 and 2 skills but doesn’t have 0 and 4 skills.
Let’s first turn the skills from strings to number IDs using unordered_map<string, int> m.
Then vector<int> p stores the bitmasks of the skills of each people.
Let dp[state][j + 1] be the min number of people required for skills represented by state if we only use people 0 to j.
For dp[state][j + 1], we have two choices:
- Skip people
j, thendp[state][j + 1] = dp[state][j] - Pick people
j, thendp[state][j + 1] = dp[prevState][j] + 1, whereprevStateisstatesubtracting all the skills peoplejhas.
dp[state][j] = min(
dp[state][j], // If we skip people `j`
dp[prevState][j] + 1 // If we pick people `j`
)
dp[0][j] = 0
dp[(1 << M) - 1][N] is the size of the answer.
To reconstruct the answer, we can start from state = (1 << M) - 1, j = N - 1.
- If
dp[state][j + 1] == dp[state][j], it means that we should skip peoplej. - Otherwise, we should pick people
j. So we pushjinto the answer, and subtract the skills peoplejhas from thestate.
We loop until state == 0.
// OJ: https://leetcode.com/problems/smallest-sufficient-team/
// Time: O(2^M * N) where M is the size of `req_skills`, N is the number of people
// Space: O(2^M * N)
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
unordered_map<string, int> m;
int M = 0, N = people.size();
for (auto &s : req_skills) m[s] = M++;
vector<int> p(N);
for (int i = 0; i < N; ++i) {
for (auto &s : people[i]) {
p[i] |= 1 << m[s];
}
}
vector<vector<int>> dp(1 << M, vector<int>(N + 1, N));
for (int i = 0; i <= N; ++i) dp[0][i] = 0;
for (int state = 0; state < 1 << M; ++state) {
for (int j = 0; j < N; ++j) {
int prev = state & ~p[j];
dp[state][j + 1] = min(dp[state][j], dp[prev][j] + 1);
}
}
vector<int> ans;
int state = (1 << M) - 1, j = N - 1;
for (; state; --j) {
if (dp[state][j + 1] == dp[state][j]) continue;
ans.push_back(j);
state &= ~p[j];
}
return ans;
}
};
Solution 2. DP
Let dp[state] be the min number of people we required for skills represented by state.
To get the optimal value of dp[state], we try each people j.
dp[state] = min( dp[prevState(j)] + 1 | prevState(j) = state & ~p[j] && 0<= j < N )
dp[0] = 0
dp[(1 << M) - 1] is the size of the answer.
To reconstruct the answer, we use pick[state] to store the people we should pick given state, and prevState[state] to store the state before we pick people pick[state].
// OJ: https://leetcode.com/problems/smallest-sufficient-team/
// Time: O(2^M * N) where M is the size of `req_skills`, N is the number of people
// Space: O(2^M + N)
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
unordered_map<string, int> m;
int M = 0, N = people.size();
for (auto &s : req_skills) m[s] = M++;
vector<int> p(N);
for (int i = 0; i < N; ++i) {
for (auto &s : people[i]) {
p[i] |= 1 << m[s];
}
}
vector<int> dp(1 << M, N), pick(1 << M, -1), prevState(1 << M);
dp[0] = 0;
for (int state = 0; state < 1 << M; ++state) {
for (int j = 0; j < N; ++j) {
int prev = state & ~p[j];
if (dp[prev] + 1 < dp[state]) {
dp[state] = dp[prev] + 1;
pick[state] = j;
prevState[state] = prev;
}
}
}
vector<int> ans;
int state = (1 << M) - 1;
while (pick[state] != -1) {
ans.push_back(pick[state]);
state = prevState[state];
}
return ans;
}
};
// OJ: https://leetcode.com/problems/smallest-sufficient-team/
// Time: O(2^M * N) where M is the size of `req_skills`, N is the number of people
// Space: O(2^M + N)
// Ref: https://leetcode.com/problems/smallest-sufficient-team/discuss/342120/C%2B%2B-DP-32ms-DP-solution.-Easy-to-implement
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
unordered_map<string, int> m;
int M = req_skills.size(), N = people.size();
for (int i = 0; i < M; ++i) m[req_skills[i]] = i;
vector<int> p(N), dp(1 << M, INT_MAX), pick(1 << M, -1), prevState(1 << M);
dp[0] = 0;
for (int i = 0; i < N; ++i) {
for (auto &s : people[i]) {
p[i] |= (1 << m[s]);
}
}
for (int state = 0; state < 1 << M; ++state) {
for (int j = 0; j < N; ++j) {
if (dp[state] == INT_MAX) continue;
int next = state | p[j];
if (dp[next] > dp[state] + 1) {
pick[next] = j;
prevState[next] = state;
dp[next] = dp[state] + 1;
}
}
}
int state = (1 << M) - 1;
vector<int> ans;
while (pick[state] != -1) {
ans.push_back(pick[state]);
state = prevState[state];
}
return ans;
}
};
-
class Solution { public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) { int skills = req_skills.length, peopleCount = people.size(); Map<String, Integer> map = new HashMap<String, Integer>(); for (int i = 0; i < skills; i++) map.put(req_skills[i], i); int[] masks = new int[peopleCount]; for (int i = 0; i < peopleCount; i++) masks[i] = getMask(people.get(i), map); int[] dp = new int[1 << skills]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; int[] prevState = new int[1 << skills]; int[] prevPerson = new int[1 << skills]; for (int i = 0; i < peopleCount; i++) { int mask = masks[i]; for (int j = (1 << skills) - 1; j >= 0; j--) { if (dp[j] != Integer.MAX_VALUE) { int newState = j | mask; if (dp[newState] > dp[j] + 1) { dp[newState] = dp[j] + 1; prevState[newState] = j; prevPerson[newState] = i; } } } } List<Integer> teamList = new ArrayList<Integer>(); int state = (1 << skills) - 1; while (state > 0) { teamList.add(prevPerson[state]); state = prevState[state]; } int teamSize = teamList.size(); int[] teamArray = new int[teamSize]; for (int i = 0; i < teamSize; i++) teamArray[i] = teamList.get(teamSize - 1 - i); return teamArray; } public int getMask(List<String> list, Map<String, Integer> map) { int mask = 0; for (String skill : list) { if (map.containsKey(skill)) mask |= 1 << map.get(skill); } return mask; } } ############ class Solution { private int m; private int n; private int[] ps; private int[][][] f; private static final int MX = 100; public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) { m = req_skills.length; n = people.size(); ps = new int[n]; f = new int[n][1 << m][]; Map<String, Integer> d = new HashMap<>(); for (int i = 0; i < m; ++i) { d.put(req_skills[i], i); } for (int i = 0; i < n; ++i) { for (String skill : people.get(i)) { ps[i] |= 1 << d.get(skill); } } return dfs(0, 0); } private int[] dfs(int i, int state) { if (i == n) { return state == (1 << m) - 1 ? new int[0] : add(new int[0], MX); } if (f[i][state] != null) { return f[i][state]; } int[] ans1 = dfs(i + 1, state); int[] ans2 = dfs(i + 1, state | ps[i]); if (ans1.length > 0 && ans1[0] == MX && ans2.length > 0 && ans2[0] == MX) { return f[i][state] = ans1; } if (ans1.length > 0 && ans1[0] == MX) { return f[i][state] = add(ans2, i); } if (ans2.length > 0 && ans2[0] == MX) { return f[i][state] = ans1; } if (ans1.length < ans2.length + 1) { return f[i][state] = ans1; } return f[i][state] = add(ans2, i); } private int[] add(int[] nums, int x) { int[] copy = Arrays.copyOf(nums, nums.length + 1); copy[copy.length - 1] = x; return copy; } } -
class Solution: def smallestSufficientTeam( self, req_skills: List[str], people: List[List[str]] ) -> List[int]: @cache def dfs(i, state): if i == n: return [] if state == (1 << m) - 1 else None ans1 = dfs(i + 1, state) ans2 = dfs(i + 1, state | ps[i]) if ans1 is None and ans2 is None: return None if ans1 is None: return [i] + ans2 if ans2 is None: return ans1 return min(ans1, [i] + ans2, key=len) d = {s: i for i, s in enumerate(req_skills)} m = len(req_skills) n = len(people) ps = [0] * n for i, skills in enumerate(people): for skill in skills: ps[i] |= 1 << d[skill] return dfs(0, 0) -
func smallestSufficientTeam(req_skills []string, people [][]string) (ans []int) { d := map[string]int{} for i, s := range req_skills { d[s] = i } m, n := len(req_skills), len(people) p := make([]int, n) for i, ss := range people { for _, s := range ss { p[i] |= 1 << d[s] } } const inf = 1 << 30 f := make([]int, 1<<m) g := make([]int, 1<<m) h := make([]int, 1<<m) for i := range f { f[i] = inf } f[0] = 0 for i := range f { if f[i] == inf { continue } for j := 0; j < n; j++ { if f[i]+1 < f[i|p[j]] { f[i|p[j]] = f[i] + 1 g[i|p[j]] = j h[i|p[j]] = i } } } for i := 1<<m - 1; i != 0; i = h[i] { ans = append(ans, g[i]) } return } -
function smallestSufficientTeam( req_skills: string[], people: string[][], ): number[] { const d: Map<string, number> = new Map(); const m = req_skills.length; const n = people.length; for (let i = 0; i < m; ++i) { d.set(req_skills[i], i); } const p: number[] = new Array(n).fill(0); for (let i = 0; i < n; ++i) { for (const s of people[i]) { p[i] |= 1 << d.get(s)!; } } const inf = 1 << 30; const f: number[] = new Array(1 << m).fill(inf); const g: number[] = new Array(1 << m).fill(0); const h: number[] = new Array(1 << m).fill(0); f[0] = 0; for (let i = 0; i < 1 << m; ++i) { if (f[i] === inf) { continue; } for (let j = 0; j < n; ++j) { if (f[i] + 1 < f[i | p[j]]) { f[i | p[j]] = f[i] + 1; g[i | p[j]] = j; h[i | p[j]] = i; } } } const ans: number[] = []; for (let i = (1 << m) - 1; i; i = h[i]) { ans.push(g[i]); } return ans; }