1125. Smallest Sufficient Team

题目信息

题号:

1125

难度:

Hard

主题:

状态压缩、动态规划、最小团队

原题:

LeetCode 1125

重点:

团队联合技能必须覆盖全部必需技能;返回人数最少的人员下标集合,顺序不限且答案保证存在

题目重述

给定互不相同的必需技能数组 req_skills,以及人员技能数组 people,其中 people[i] 列出第 i 个人掌握的技能。每个人的技能都来自 req_skills,一个人也可能没有任何技能。

选择若干人员组成团队,使团队成员技能的并集覆盖全部必需技能。请返回人数最少的充分团队所包含的人员下标;若存在多个最小团队,可返回任意一个,顺序不限。

1 <= req_skills.length <= 16,1 <= people.length <= 60;每项技能字符串长度在 [1,16],同一数组内部技能互不重复,并保证存在充分团队。

自建示例

两人组合覆盖三项技能:

输入:req_skills = ["a","b","c"], people = [["a","b"],["b","c"],["a"],["c"]]
输出:[0,3]
解释:人员 0 覆盖 a、b,人员 3 覆盖 c,两人即可覆盖全部技能;不存在单人覆盖三项技能。也可以返回 [1,2]。

无技能人员不需要入选:

输入:req_skills = ["x"], people = [[],["x"],["x"]]
输出:[1]
解释:任意一个掌握 x 的人即可构成最小团队;人员 0 不提供技能。