In a project, you have a list of required skills req_skills, and a list of people. The ith person people[i] contains a list of skills that the person has.
Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.
team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].Return any sufficient team of the smallest possible size, represented by the index of each person. You may return the answer in any order.
It is guaranteed an answer exists.
Example 1:
Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]] Output: [0,2]
Example 2:
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]
Constraints:
1 <= req_skills.length <= 161 <= req_skills[i].length <= 16req_skills[i] consists of lowercase English letters.req_skills are unique.1 <= people.length <= 600 <= people[i].length <= 161 <= people[i][j].length <= 16people[i][j] consists of lowercase English letters.people[i] are unique.people[i] is a skill in req_skills.This approach leverages a bitmask along with dynamic programming to solve the problem of finding the smallest sufficient team. We use a bitmask to represent the combination of skills possessed by a team. Dynamic programming is employed to track the smallest team for every possible combination of skills, allowing us to build up to a team that covers all required skills.
The code utilizes a dictionary, skill_index, to map each skill to a unique index. We then define a dynamic programming dictionary, dp, where each key represents a set of skills (using bitmask), and value is the team of indices representing people with these skills.
For each person, we calculate the his_skill bitmask, which marks the skills this person can cover. We iterate over each entry in our dynamic programming table, updating it with the new combinations of skills that could be formed by adding the current person.
The result is found in dp[(1 << n) - 1], where n is the length of req_skills, representing the full set of skills covered.
C++
JavaScript
Time Complexity: O(people.length * 2^n), where n is the number of required skills. Space Complexity: O(2^n).
This approach utilizes backtracking to explore all possible combinations of people in attempting to form the smallest team covering all required skills. We prune branches once we find a valid team, retaining the best (smallest) solution observed so far.
This Java implementation uses recursion to explore the assembly of teams in a backtracking manner. We map each skill to a bit index, then convert each person's skills to a bitmask. We recursively decide whether to include each person in the current team, pruning branches that exceed the current smallest team's size or cannot complete the skill set. The smallest sufficient team is stored in bestTeam.
C#
Time Complexity: O(2^people.length), worst case exploring all combinations. Space Complexity: O(people.length) due to recursive depth.
| Approach | Complexity |
|---|---|
| Bitmask with Dynamic Programming | Time Complexity: O(people.length * 2^n), where n is the number of required skills. Space Complexity: O(2^n). |
| Backtracking | Time Complexity: O(2^people.length), worst case exploring all combinations. Space Complexity: O(people.length) due to recursive depth. |
Smallest Range Covering Elements from K Lists - Leetcode 632 - Python • NeetCodeIO • 14,731 views views
Watch 9 more video solutions →Practice Smallest Sufficient Team with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor