← Static tasks

1125. Smallest Sufficient Team

leetcode hard

#array#bit-manipulation#csharp#dynamic-programming#hard#hash-table#leetcode#string

Task

В проекте у вас есть список необходимых навыков req_skills и список людей. i-й человек people[i] содержит список навыков, которыми обладает этот человек.

Рассмотрим достаточную команду: набор людей, такой что для каждого необходимого навыка из req_skills, есть по крайней мере один человек в команде, который обладает этим навыком. Мы можем представить эти команды индексами каждого человека.

Например, команда = [0, 1, 3] представляет людей с навыками people[0], people[1] и people[3].

Верните любую достаточную команду наименьшего возможного размера, представленную индексами каждого человека. Вы можете вернуть ответ в любом порядке.

Гарантируется, что ответ существует.

Пример:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"],

people = [["algorithms","math","java"],["algorithms","math","reactjs"],

["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]

Output: [1,2]

C# solution

matched/original
public class Solution {
    public int[] SmallestSufficientTeam(string[] req_skills, IList<IList<string>> people) {
        int n = people.Count, m = req_skills.Length;
        var skillId = new Dictionary<string, int>();
        for (int i = 0; i < m; i++) {
            skillId[req_skills[i]] = i;
        }
        var skillsMaskOfPerson = new int[n];
        for (int i = 0; i < n; i++) {
            foreach (var skill in people[i]) {
                if (skillId.ContainsKey(skill)) {
                    skillsMaskOfPerson[i] |= 1 << skillId[skill];
                }
            }
        }
        var dp = new long[1 << m];
        Array.Fill(dp, (1L << n) - 1);
        dp[0] = 0;
        for (int skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
            for (int i = 0; i < n; i++) {
                int smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
                if (smallerSkillsMask != skillsMask) {
                    long peopleMask = dp[smallerSkillsMask] | (1L << i);
                    if (BitCount(peopleMask) < BitCount(dp[skillsMask])) {
                        dp[skillsMask] = peopleMask;
                    }
                }
            }
        }
        long answerMask = dp[(1 << m) - 1];
        var ans = new List<int>();
        for (int i = 0; i < n; i++) {
            if (((answerMask >> i) & 1) == 1) {
                ans.Add(i);
            }
        }
        return ans.ToArray();
    }
    private int BitCount(long value) {
        int count = 0;
        while (value != 0) {
            value &= (value - 1);
            count++;
        }
        return count;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& SmallestSufficientTeam(vector<string> req_skills, IList<vector<string>> people) {
        int n = people.size(), m = req_skills.size();
        var skillId = new unordered_map<string, int>();
        for (int i = 0; i < m; i++) {
            skillId[req_skills[i]] = i;
        }
        var skillsMaskOfPerson = new int[n];
        for (int i = 0; i < n; i++) {
            foreach (var skill in people[i]) {
                if (skillId.count(skill)) {
                    skillsMaskOfPerson[i] |= 1 << skillId[skill];
                }
            }
        }
        var dp = new long[1 << m];
        Array.Fill(dp, (1L << n) - 1);
        dp[0] = 0;
        for (int skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
            for (int i = 0; i < n; i++) {
                int smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
                if (smallerSkillsMask != skillsMask) {
                    long peopleMask = dp[smallerSkillsMask] | (1L << i);
                    if (BitCount(peopleMask) < BitCount(dp[skillsMask])) {
                        dp[skillsMask] = peopleMask;
                    }
                }
            }
        }
        long answerMask = dp[(1 << m) - 1];
        var ans = new List<int>();
        for (int i = 0; i < n; i++) {
            if (((answerMask >> i) & 1) == 1) {
                ans.push_back(i);
            }
        }
        return ans.ToArray();
    }
    private int BitCount(long value) {
        int count = 0;
        while (value != 0) {
            value &= (value - 1);
            count++;
        }
        return count;
    }
}

Java solution

matched/original
class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = people.size(), m = req_skills.length;
        HashMap<String, Integer> skillId = new HashMap<String, Integer>();
        for (int i = 0; i < m; i++) {
            skillId.put(req_skills[i], i);
        }
        int skillsMaskOfPerson[] = new int[n];
        for (int i = 0; i < n; i++) {
            for (String skill : people.get(i)) {
                skillsMaskOfPerson[i] |= 1 << skillId.get(skill);
            }
        }
        long dp[] = new long [1 << m];
        Arrays.fill(dp, (1L << n) - 1);
        dp[0] = 0;
        for (int skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
            for (int i = 0; i < n; i++) {
                int smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
                if (smallerSkillsMask != skillsMask) {
                    long peopleMask = dp[smallerSkillsMask] | (1L << i);
                    if (Long.bitCount(peopleMask) < Long.bitCount(dp[skillsMask])) {
                        dp[skillsMask] = peopleMask;
                    }
                }
            }
        }
        long answerMask = dp[(1 << m) - 1];
        int ans[] = new int [Long.bitCount(answerMask)];
        int ptr = 0;
        for (int i = 0; i < n; i++) {
            if (((answerMask >> i) & 1) == 1) {
                ans[ptr++] = i;
            }
        }
        return ans;
    }
}

JavaScript solution

matched/original
var smallestSufficientTeam = function(req_skills, people) {
    const n = people.length, m = req_skills.length;
    const skillId = new Map(req_skills.map((skill, i) => [skill, i]));
    const skillsMaskOfPerson = Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        for (const skill of people[i]) {
            if (skillId.has(skill)) {
                skillsMaskOfPerson[i] |= 1 << skillId.get(skill);
            }
        }
    }
    const dp = Array(1 << m).fill((1 << n) - 1);
    dp[0] = 0;
    for (let skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
        for (let i = 0; i < n; i++) {
            const smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
            if (smallerSkillsMask !== skillsMask) {
                const peopleMask = dp[smallerSkillsMask] | (1 << i);
                if (bitCount(peopleMask) < bitCount(dp[skillsMask])) {
                    dp[skillsMask] = peopleMask;
                }
            }
        }
    }
    const answerMask = dp[(1 << m) - 1];
    const result = [];
    for (let i = 0; i < n; i++) {
        if ((answerMask >> i) & 1) {
            result.push(i);
        }
    }
    return result;
};

function bitCount(n) {
    let count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Python solution

matched/original
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(people)
        m = len(req_skills)
        skillId = {skill: i for i, skill in enumerate(req_skills)}
        skillsMaskOfPerson = [0] * n
        for i in range(n):
            for skill in people[i]:
                if skill in skillId:
                    skillsMaskOfPerson[i] |= 1 << skillId[skill]
        
        dp = [(1 << n) - 1] * (1 << m)
        dp[0] = 0
        for skillsMask in range(1, 1 << m):
            for i in range(n):
                smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i]
                if smallerSkillsMask != skillsMask:
                    peopleMask = dp[smallerSkillsMask] | (1 << i)
                    if bin(peopleMask).count('1') < bin(dp[skillsMask]).count('1'):
                        dp[skillsMask] = peopleMask
        
        answerMask = dp[(1 << m) - 1]
        return [i for i in range(n) if (answerMask >> i) & 1]

Go solution

matched/original
import "math/bits"

func smallestSufficientTeam(req_skills []string, people [][]string) []int {
    n, m := len(people), len(req_skills)
    skillId := make(map[string]int)
    for i, skill := range req_skills {
        skillId[skill] = i
    }
    skillsMaskOfPerson := make([]int, n)
    for i, person := range people {
        for _, skill := range person {
            if id, ok := skillId[skill]; ok {
                skillsMaskOfPerson[i] |= 1 << id
            }
        }
    }
    dp := make([]int64, 1<<m)
    for i := range dp {
        dp[i] = (1 << n) - 1
    }
    dp[0] = 0
    for skillsMask := 1; skillsMask < (1 << m); skillsMask++ {
        for i := 0; i < n; i++ {
            smallerSkillsMask := skillsMask &^ skillsMaskOfPerson[i]
            if smallerSkillsMask != skillsMask {
                peopleMask := dp[smallerSkillsMask] | (1 << i)
                if bits.OnesCount64(uint64(peopleMask)) < bits.OnesCount64(uint64(dp[skillsMask])) {
                    dp[skillsMask] = peopleMask
                }
            }
        }
    }
    answerMask := dp[(1<<m)-1]
    result := []int{}
    for i := 0; i < n; i++ {
        if (answerMask>>i)&1 == 1 {
            result = append(result, i)
        }
    }
    return result
}

Explanation

Algorithm

1⃣Инициализация и создание масок навыков:

Определите количество людей n и количество необходимых навыков m.

Создайте хэш-таблицу skillId, чтобы сопоставить каждому навыку уникальный индекс.

Создайте массив skillsMaskOfPerson, который будет содержать битовые маски навыков для каждого человека.

2⃣Динамическое программирование (DP):

Создайте массив dp размера 2^m и заполните его значениями (1 << n) - 1.

Установите dp[0] в 0 (базовый случай).

Для каждого skillsMask от 1 до 2^m - 1:

- для каждого человека i:

- вычислите smallerSkillsMask как skillsMask & ~skillsMaskOfPerson[i].

- если smallerSkillsMask отличается от skillsMask, обновите dp[skillsMask], если новая команда лучше (имеет меньше установленных битов).

3⃣Формирование ответа:

Извлеките ответ из dp и верните массив индексов людей, составляющих минимальную достаточную команду.

😎