Smallest Sufficient Team

给一个数组, 里面是完成一个任务需要的技能, 另一个数组是每个人有的技能, 求完成任务的最少人的数组. 这个题是一个set cover问题, 因为set cover的k决定性问题是NPC, 但是set cover本身不是, 所以这个题应该可以在多项式时间内解决. 首先hints中提示了要做bit编码, 那么就用过反转index,找到每个skill对应的数字, 然后通过左移(<<)标记在int中. 然后就是算法部分. 通过hint2得知, 这题是类似于背包问题的dp问题, 所以我们用一个loop扫描每个人, 然后用一个数组装所有可能的需要完成任务的技能的combination, 比如n个需要的技能, 那么就是 1 << 个位置. 所以我们的答案就在all[(1<<n) – 1]这个位置上.我们比较每个可能技能下的需要的人数, 就可以得知这种组合下的人的最优解(人数最少).

最后要解决的问题是, 如何匹配组合的技能和人的技能.int comb = k | pSkill; k遍历所有的技能, 然后通过与运算和pSkill进行匹配. 对技能的编码如下: {"java":0,"nodejs":1,"reactjs":2} ,

而pSkill的编码比如people: [["java","nodejs","reactjs"]] 编码为111. 即表示这个人会所有技能, 那么如果是 people: [["java","reactjs"]], 编码为101,

k则从1一直遍历到1 << 3,也就是7(111), 这样可以覆盖所有可能的组合, 我们通过k一直update每个人的技能与当前team的匹配结果, 最后得出答案.

class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = req_skills.length;
        int m = people.size();
        List<Integer>[] all = new ArrayList[1 << n];
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            map.put(req_skills[i], i); // build reverse index
        }
        for(int i = 0 ; i < all.length; i++) {
            all[i] = new ArrayList<>();
        }
        for(int p = 0; p < m; p++) {
            int pSkill = 0; // one person's skill
            for(String s : people.get(p))
                pSkill |= 1 << (map.get(s));
            for(int k = 0; k < all.length; k++) {
                if(k != 0 && all[k].size() == 0) // haven't visited yet
                    continue;
                List<Integer> cur = all[k];
                int comb = k | pSkill;
                if(comb == k) // in this case, pSkill is same to k
                    continue;
                int size = all[comb].size();
                if(size == 0 || size > cur.size() + 1) {
                    List<Integer> newList = new ArrayList<>(cur);
                    newList.add(p);
                    all[comb] = newList;
                }
            }
        }
        
        int[] res = new int[all[(1 << n) - 1].size()];
        for(int i = 0 ; i < all[(1<<n) - 1].size(); i++) {
            res[i] = all[(1<<n) - 1].get(i);
        }
        return res;
    
    }
}