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的匹配结果, 最后得出答案.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
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; } } |