Ctrl K

Самая маленькая команда со всеми навыками

Сложная
Вы собираете команду под проект. Для него нужны навыки из списка skills (все названия различны). Есть кандидаты: candidates[i] — список навыков i-го кандидата. Команда подходит, если каждый навык из skills есть хотя бы у одного её участника. Найдите подходящую команду из наименьшего возможного числа людей и верните номера её участников (нумерация с нуля) в любом порядке. Гарантируется, что подходящая команда существует и самая маленькая команда ровно одна.
Пример 1
skills=['sql', 'python', 'excel'], candidates=[['sql'], ['python', 'excel'], ['excel']] → [1, 0]

Первый знает sql, второй — python и excel: вдвоём они закрывают все три навыка. Одного человека со всеми тремя навыками нет.

Пример 2
skills=['go', 'k8s', 'aws', 'figma'], candidates=[['go', 'k8s'], ['aws'], ['figma'], ['k8s', 'aws', 'figma']] → [3, 0]

Кандидат 3 закрывает k8s, aws и figma, а go есть только у кандидата 0. Вдвоём они справляются, а одного человека со всеми навыками нет.

Пример 3
skills=['ml'], candidates=[[], ['ml']] → [1]

У кандидата 0 нет нужных навыков, хватает одного кандидата 1.

Ограничения
  • 1 ≤ len(skills) ≤ 16
  • 1 ≤ len(skills[i]) ≤ 16, только строчные латинские буквы и цифры; все строки skills различны
  • 1 ≤ len(candidates) ≤ 60
  • 0 ≤ len(candidates[i]) ≤ 16; навыки одного кандидата различны и все входят в skills
  • Подходящая команда существует, и команда наименьшего размера единственна
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКак рассчитаться за меньше переводов СложнаяДве группы с одинаковым средним СложнаяСклейка фрагментов СложнаяЦепочки с квадратными суммами СложнаяЛучший набор слов из фишек Сложная
загружаем Python…
Вход
skills=['sql', 'python', 'excel'], candidates=[['sql'], ['python', 'excel'], ['excel']]
Ожидается
[1, 0]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 40 тестов на сервере, включая скрытые.