1125. Smallest Sufficient Team¶
题目信息¶
- 题号:
1125
- 难度:
Hard
- 主题:
状态压缩、动态规划、最小团队
- 原题:
- 重点:
团队联合技能必须覆盖全部必需技能;返回人数最少的人员下标集合,顺序不限且答案保证存在
题目重述¶
给定互不相同的必需技能数组 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 不提供技能。