原文链接: https://leetcode-cn.com/problems/smallest-sufficient-team

英文原文

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.

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 <= req_skills[i].length <= 16
• req_skills[i] consists of lowercase English letters.
• All the strings of req_skills are unique.
• 1 <= people.length <= 60
• 0 <= people[i].length <= 16
• 1 <= people[i][j].length <= 16
• people[i][j] consists of lowercase English letters.
• All the strings of people[i] are unique.
• Every skill in people[i] is a skill in req_skills.
• It is guaranteed a sufficient team exists.

中文题目

作为项目经理，你规划了一份需求的技能清单 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 中的技能
• 题目数据保证「必要团队」一定存在

通过代码

高赞题解

思路：

本题是一个 集合覆盖问题，决定性问题 的集合覆盖是 NP完全问题，最佳化问题的集合覆盖是NP困难问题。所以想得到最优解（之一），只能用暴力搜索。好在数据范围并不大，最大状态空间也只有 $2^{16}=65,536‬$ 种状态，也就是 $16$ 个人每个人有选和不选两种情况。我们可以用动态规划的方法进行搜索。先将 req_skills 的全集建立一个字典，对每个技能进行编号 0 ~ n-1 。然后建立 dp 数组，长度为 $2^n$ ，数组元素初始化为 people 的全集，然后对 dp[0] 初始化为空集。然后我们遍历每个人，对于所有状态，计算把这个人加入团队后，整个团队的技能是否增加，如果增加并且人数比拥有相同技能的团队更优化，则更新结果。最终，全集 dp[(1 << n) - 1] 中的 people 集合就是我们要求的结果。

代码：

[-Python]
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        # 为skills建立字典
        n = len(req_skills)
        d = dict()
        for i in range(n):
            d[req_skills[i]] = i
        # 所有状态
        dp = [list(range(len(people))) for _ in range(1 << n)]
        dp[0] = []
        # 遍历所有人
        for i in range(len(people)):
            # 求这个人的技能
            skill = 0
            for s in people[i]:
                skill |= (1 << d[s])
            for k, v in enumerate(dp):
                # 把这个人加入进来以后的团队技能
                new_skills = k | skill
                # 如果团队技能因此而增加 并且增加后的人数比新技能原来的人数少 则更新答案
                if new_skills != k and len(dp[new_skills]) > len(v) + 1:
                    dp[new_skills] = v + [i]
        return dp[(1 << n) - 1]

统计信息

通过次数	提交次数	AC比率
3160	6387	49.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言