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

😎 Решение:

class Solution {
    function smallestSufficientTeam($req_skills, $people) {
        $n = count($people);
        $m = count($req_skills);
        $skillId = array_flip($req_skills);
        $skillsMaskOfPerson = array_fill(0, $n, 0);

        foreach ($people as $i => $person) {
            foreach ($person as $skill) {
                if (isset($skillId[$skill])) {
                    $skillsMaskOfPerson[$i] |= 1 << $skillId[$skill];
                }
            }
        }

        $dp = array_fill(0, 1 << $m, (1 << $n) - 1);
        $dp[0] = 0;

        for ($skillsMask = 1; $skillsMask < (1 << $m); $skillsMask++) {
            foreach ($skillsMaskOfPerson as $i => $mask) {
                $smallerSkillsMask = $skillsMask & ~$mask;
                if ($smallerSkillsMask != $skillsMask) {
                    $peopleMask = $dp[$smallerSkillsMask] | (1 << $i);
                    if (substr_count(decbin($peopleMask), '1') < substr_count(decbin($dp[$skillsMask]), '1')) {
                        $dp[$skillsMask] = $peopleMask;
                    }
                }
            }
        }

        $answerMask = $dp[(1 << $m) - 1];
        $result = [];
        for ($i = 0; $i < $n; $i++) {
            if (($answerMask >> $i) & 1) {
                $result[] = $i;
            }
        }
        return $result;
    }
}

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