最小的必要团队

难度: Hard

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

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

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

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

示例 1：

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

示例 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 中的技能
题目数据保证「必要团队」一定存在

Submission

运行时间: 59 ms

内存: 0.0 MB

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        m, n = (1 << len(req_skills)) - 1, len(req_skills)
        ski = {skill: i for i, skill in enumerate(req_skills)}
        
        skp, psk = [set() for _ in req_skills], [0] * len(people)
        for i, p in enumerate(people):
            for k in p:
                skp[ski[k]].add(i)
                psk[i] |= 1 << ski[k]

        @cache
        def dp(i: int, hit: int):
            if i == n or hit == m:
                return []
            if (hit >> i) & 1:
                return dp(i + 1, hit)
            return min(([p] + dp(i + 1, hit | psk[p]) for p in skp[i]), key=len)

        return dp(0, 0)

Explain

这个问题可以通过动态规划求解，利用位掩码来表示技能集。使用一个整数的不同位来代表不同的技能，如果某位为1，则表示拥有该技能。首先，为每个技能建立一个映射，将技能映射到一个索引（即位位置）。然后为每个人创建一个位掩码，表示他们拥有的技能。对于每个技能，维护一个集合，包含所有拥有该技能的人员索引。定义一个递归函数 dp(i, hit)，其中 i 表示当前考虑的技能索引，hit 是一个位掩码，表示已覆盖的技能集。如果当前技能已被覆盖，即(hit >> i) & 1 为真，则直接处理下一个技能。否则，尝试通过添加拥有当前技能的人来更新 hit。最终，递归的目标是找到覆盖所有技能的最小团队。使用 @cache 装饰器来缓存递归结果，避免重复计算。

时间复杂度: O(n * 2^n * 60)

空间复杂度: O(2^n * n)

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        m, n = (1 << len(req_skills)) - 1, len(req_skills)
        ski = {skill: i for i, skill in enumerate(req_skills)}
        
        skp, psk = [set() for _ in req_skills], [0] * len(people)
        for i, p in enumerate(people):
            for k in p:
                skp[ski[k]].add(i)
                psk[i] |= 1 << ski[k]
        
        @cache
        def dp(i: int, hit: int):
            if i == n or hit == m: # 所有技能已覆盖
                return []
            if (hit >> i) & 1: # 当前技能已覆盖
                return dp(i + 1, hit)
            return min(([p] + dp(i + 1, hit | psk[p]) for p in skp[i]), key=len) # 尝试每个有技能的人
        
        return dp(0, 0)

Explore

`dp(i, hit)`是一个动态规划函数，其中`i`表示当前正在考虑的技能索引，`hit`是一个位掩码，表示到目前为止已经被覆盖的技能集。在此问题中，每个技能对应一个位，如果某个技能已被覆盖，则`hit`中相应的位为1，否则为0。因此，`hit`可以精确地表示出哪些技能已经被团队成员的集合覆盖。

使用位掩码`hit`来表示已覆盖的技能集可以让状态表示更为紧凑和高效。位掩码允许我们用一个整型数值来表示所有技能的覆盖情况，这样可以极大地简化状态的存储和操作。此外，位运算（如位与、位或和位移等）通常比其他形式的数据操作更快，这对于求解涉及多种可能组合的动态规划问题特别有利。

在递归函数`dp(i, hit)`中，判断是否需要继续递归到下一个技能主要依据当前技能是否已被覆盖。通过检查`hit`位掩码中当前技能对应的位是否为1（即检查`(hit >> i) & 1`是否为真）来确定。如果当前技能已被覆盖，则函数调用自身对下一个技能进行递归（即`dp(i + 1, hit)`）。如果当前技能未被覆盖，则尝试添加不同的拥有该技能的人，更新`hit`，并递归求解。

使用`min`函数和`key=len`来选择最小的团队是一种有效的方法，因为它确保在所有可能的团队配置中选取成员数最少的一个。这种方法直接针对问题的目标进行优化。然而，在效率方面，这种方法可能在某些情况下表现不佳，尤其是当候选团队数量很大时。虽然使用缓存（如`@cache`装饰器）可以显著提高递归调用的效率，但计算每个技能的所有可能团队配置仍可能导致高时间复杂度。更优的策略可能包括更高效的剪枝技术，在递归过程中更早地排除明显不优的选项，或者使用启发式或近似算法来找到足够好的解而非最优解。