题目描述

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

• 例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。

请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

样例

输入：req_skills = ["java","nodejs","reactjs"],
people = [["java"],["nodejs"],["nodejs","reactjs"]]
输出：[0,2]

输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"],
people = [
    ["algorithms","math","java"],
    ["algorithms","math","reactjs"],
    ["java","csharp","aws"],
    ["reactjs","csharp"],
    ["csharp","math"],["aws","java"]
]
输出：[1,2]

限制

• 1 <= req_skills.length <= 16
• 1 <= req_skills[i].length <= 16
• req_skills[i] 由小写英文字母组成。
• req_skills 中的所有字符串 互不相同。
• 1 <= people.length <= 60
• 0 <= people[i].length <= 16
• 1 <= people[i][j].length <= 16
• people[i][j] 由小写英文字母组成。
• people[i] 中的所有字符串 互不相同。
• people[i] 中的每个技能是 req_skills 中的技能。
• 题目数据保证「必要团队」一定存在。

算法

(01背包，状态压缩动态规划) $O(mL + npL + n \cdot 2^m)$

1. 我们将每个技能从 $0$ 开始进行编号，假设共 $m$ 个，每个人掌握的技能可以用一个数来表示，这个数的二进制就是掌握的技能列表。
2. 设状态 $f(i, mask)$ 表示能遍历 $i$ 个人，满足技能集合为 $mask$ 的最少人数。$mask$ 是一个整数表示的集合，其二进制表示一个技能列表。
3. 初始时，$f(0, {}) = 0$，其余为正无穷。
4. 转移时，对于第 $i$ 个人和技能集合 $mask$，由于前驱状态不好计算，所以直接找后继状态，可以更新 $f(mask \text{ OR } p(i)) = \min(f(mask \text{ OR } p(i)), f(mask) + 1)$。其中 $p(i)$ 表示第 $i$ 个人技能列表的二进制整数值。
5. 最终最优团队的个数为 $f(n, 2^m - 1)$，可以使用倒序枚举 $mask$ 来优化掉第一位的状态表示，参考 01 背包的优化。
6. 假设使用了一维状态表示，接下来需要找答案。我们在转移时，记录每次的更新过程，如果发生了最小值的更新，则记录 $gi(mask \text{ OR } p(i)) = i, gm(mask \text{ OR } p(i)) = mask$，表示 $mask \text{ OR } p(i)$ 这个状态是从第 $i$ 个人，和集合 $mask$ 转移过去的。然后找答案就可以倒序迭代，从 $mask = 2^m - 1$ 开始，直到 $0$，每次加入 $gi(mask)$ 就是选择的答案，然后更新 $mask = gm(mask)$。

时间复杂度

• 预处理需要 $O(mL + npL)$ 的时间，其中 $L$ 为字符串的长度，$p$ 为每个人所拥有的技能个数。
• 动态规划状态数为 $O(n \cdot 2^m)$，转移时间为常数。
• 故总时间复杂度为 $O(mL + npL + n \cdot 2^m)$。

空间复杂度

• 需要 $O(mL + 2^m)$ 的额外空间存储哈希表和动态规划的状态。

C++ 代码

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills,
        vector<vector<string>>& people
    ) {
        const int m = req_skills.size();
        const int n = people.size();
        const int INF = 1000000000;

        unordered_map<string, int> h;
        for (int i = 0; i < m; i++)
            h[req_skills[i]] = i;

        vector<int> f(1 << m, INF);
        vector<int> gi(1 << m), gm(1 << m);

        f[0] = 0;
        for (int i = 0; i < n; i++) {
            int p = 0;
            for (const auto &s : people[i])
                p |= 1 << h[s];

            for (int mask = (1 << m) - 1; mask >= 0; mask--) {
                int new_mask = mask | p;

                if (f[new_mask] > f[mask] + 1) {
                    f[new_mask] = f[mask] + 1;
                    gi[new_mask] = i;
                    gm[new_mask] = mask;
                }
            }
        }

        vector<int> ans;
        for (int mask = (1 << m) - 1; mask > 0; mask = gm[mask])
            ans.push_back(gi[mask]);

        return ans;
    }
};