项目组建问题

[题目链接](https://www.nowcoder.com/practice/e363e99bc8144436b4e0f0b8f1ed481d)

思路

给定项目所需的开发角色编号数组 reqSkills，以及每位工程师能承担的角色数组 peoSkills，要求选出人数最少的工程师组合，使其技能并集覆盖所有所需角色。若存在多种最少人数方案，输出编号字典序最小的。

状压 DP

所需角色数量有限（最多 20 左右），可以用位掩码表示角色覆盖状态。

1. 角色编号映射：将 reqSkills 中每个角色映射到一个比特位 。目标状态为 （全部覆盖）。

1. 工程师技能掩码：将每位工程师的技能转换为对应的位掩码 personMask[i]。

1. DP 转移：令 dp[mask] 表示覆盖状态恰好为 mask 时所需的最少人数及对应的工程师编号列表。初始 dp[0] = (0, [])。

对每个已到达的状态 mask，枚举每位工程师 ：

- 计算 newMask = mask | personMask[i]

- 若 newMask == mask（无新技能），跳过

- 若 dp[mask].size + 1 < dp[newMask].size，更新

- 若人数相同，保留字典序更小的组合

1. 字典序保证：由于按工程师编号从小到大枚举，且每次追加的编号递增，所以团队列表天然有序，直接比较即可。

复杂度

• 时间：，其中 为所需角色数， 为工程师人数。
• 空间：， 为最小团队规模。

代码

C++

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<int>& reqSkills, vector<vector<int> >& peoSkills) {
        unordered_map<int, int> skillIndex;
        int n = reqSkills.size();
        for (int i = 0; i < n; i++) {
            skillIndex[reqSkills[i]] = i;
        }

        int target = (1 << n) - 1;
        int m = peoSkills.size();

        vector<int> personMask(m, 0);
        for (int i = 0; i < m; i++) {
            for (int s : peoSkills[i]) {
                if (skillIndex.count(s)) {
                    personMask[i] |= (1 << skillIndex[s]);
                }
            }
        }

        vector<int> dpSize(target + 1, INT_MAX);
        vector<vector<int>> dpTeam(target + 1);
        dpSize[0] = 0;

        for (int mask = 0; mask <= target; mask++) {
            if (dpSize[mask] == INT_MAX) continue;
            for (int i = 0; i < m; i++) {
                int newMask = mask | personMask[i];
                if (newMask == mask) continue;
                int newSize = dpSize[mask] + 1;
                if (newSize < dpSize[newMask]) {
                    dpSize[newMask] = newSize;
                    dpTeam[newMask] = dpTeam[mask];
                    dpTeam[newMask].push_back(i + 1);
                } else if (newSize == dpSize[newMask]) {
                    vector<int> candidate = dpTeam[mask];
                    candidate.push_back(i + 1);
                    if (candidate < dpTeam[newMask]) {
                        dpTeam[newMask] = candidate;
                    }
                }
            }
        }

        return dpTeam[target];
    }
};

Java

import java.util.*;

public class Solution {
    public int[] smallestSufficientTeam(int[] reqSkills, ArrayList<ArrayList<Integer>> peoSkills) {
        HashMap<Integer, Integer> skillIndex = new HashMap<>();
        int n = reqSkills.length;
        for (int i = 0; i < n; i++) {
            skillIndex.put(reqSkills[i], i);
        }

        int target = (1 << n) - 1;
        int m = peoSkills.size();

        int[] personMask = new int[m];
        for (int i = 0; i < m; i++) {
            for (int s : peoSkills.get(i)) {
                if (skillIndex.containsKey(s)) {
                    personMask[i] |= (1 << skillIndex.get(s));
                }
            }
        }

        int[] dpSize = new int[target + 1];
        int[][] dpTeam = new int[target + 1][];
        Arrays.fill(dpSize, Integer.MAX_VALUE);
        dpSize[0] = 0;
        dpTeam[0] = new int[0];

        for (int mask = 0; mask <= target; mask++) {
            if (dpSize[mask] == Integer.MAX_VALUE) continue;
            for (int i = 0; i < m; i++) {
                int newMask = mask | personMask[i];
                if (newMask == mask) continue;
                int newSize = dpSize[mask] + 1;
                if (newSize < dpSize[newMask]) {
                    dpSize[newMask] = newSize;
                    dpTeam[newMask] = Arrays.copyOf(dpTeam[mask], dpTeam[mask].length + 1);
                    dpTeam[newMask][dpTeam[mask].length] = i + 1;
                } else if (newSize == dpSize[newMask]) {
                    int[] candidate = Arrays.copyOf(dpTeam[mask], dpTeam[mask].length + 1);
                    candidate[dpTeam[mask].length] = i + 1;
                    if (compareLex(candidate, dpTeam[newMask]) < 0) {
                        dpTeam[newMask] = candidate;
                    }
                }
            }
        }

        return dpTeam[target];
    }

    private int compareLex(int[] a, int[] b) {
        int len = Math.min(a.length, b.length);
        for (int i = 0; i < len; i++) {
            if (a[i] != b[i]) return a[i] - b[i];
        }
        return a.length - b.length;
    }
}