Задача: 1125. Smallest Sufficient Team
Сложность: hard

В проекте у вас есть список необходимых навыков 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]

👨‍💻 Алгоритм:

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 и верните массив индексов людей, составляющих минимальную достаточную команду.

😎 Решение:

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;
}

Ставь 👍 и забирай 📚 Базу знаний