1125

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 <= 16
• 1 <= people.length <= 60
• 1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
• Elements of req_skills and people[i] are (respectively) distinct.
• req_skills[i][j], people[i][j][k] are lowercase English letters.
• Every skill in people[i] is a skill in req_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:

1. Skip people j, then dp[state][j + 1] = dp[state][j]
2. Pick people j, then dp[state][j + 1] = dp[prevState][j] + 1, where prevState is state subtracting all the skills people j has.

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 people j.
• Otherwise, we should pick people j. So we push j into the answer, and subtract the skills people j has from the state.

We loop until state == 0.

// OJ: https://leetcode.com/problems/smallest-sufficient-team/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
    }
};