Сложность: 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 и верните массив индексов людей, составляющих минимальную достаточную команду.
😎 Решение:
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;
}
}Ставь 👍 и забирай 📚 Базу знаний