Skip to content

Latest commit

 

History

History
96 lines (73 loc) · 3.16 KB

1125.smallest-sufficient-team.md

File metadata and controls

96 lines (73 loc) · 3.16 KB

作为项目经理，你规划了一份需求的技能清单  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 <= people.length <= 60
  • 1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
  • req_skills  和  people[i]  中的元素分别各不相同
  • req_skills[i][j], people[i][j][k]  都由小写英文字母组成
  • 本题保证「必要团队」一定存在

算法思路

状态压缩 DP

$f[i]$ 表示状态为 $i$ 所需要的最少人员

state(k) 表示 每个团队成员的技能状态

for i ∈ [0, 2^n) 枚举所有状态

​ for j ∈ [0, n) if !(i>>j&1) 枚举缺少的技能

​ for k ∈ [0, n) 枚举所有人员，如果存在缺少的技能

​ $f[i|state(k)] = min(f[i] + 1)$

​

求最优方案，需要记录 中间状态 $path[i|state(k)] = {i, k}$

代码实现

class Solution {

    public int[] smallestSufficientTeam(String[] skills, List<List<String>> people) {
        int n = skills.length, M = 1<< n, P = 60;
        int[]f = new int[M];
        int[][]pre = new int[M][2];
        int state[] = new int[P];

        Map<String, Integer> mp = new HashMap<>();
        for (int i =0; i< skills.length; i++){
            mp.put(skills[i], i);
        }

        for (int i = 0; i< people.size(); i++){
            for (int j =0; j< people.get(i).size(); j++){
                state[i] += 1 << mp.get(people.get(i).get(j));
            }
        }

        Arrays.fill(f, 20);
        f[0] = 0;
        for (int i = 0; i< 1<< n; i++){
            for (int k =0; k< people.size(); k++){
                if ((state[k] | i) > i) {
                    if (f[i] + 1 < f[i | state[k]]){
                        f[i | state[k]] = Math.min(f[i | state[k]], f[i] + 1);
                        pre[i | state[k]][0] = i;
                        pre[i | state[k]][1] = k;
                    }
                }
            }
        }

        int[] res = new int[f[(1<<n) -1]];

        for (int i = (1<<n) -1, j = 0; i!=0;j++) {
            res[j] = pre[i][1];
            i = pre[i][0];
        }
        return res;
    }
}