Problem¶

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.

For example, 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.

Constraints:

1 <= req_skills.length <= 16
1 <= req_skills[i].length <= 16
req_skills[i] consists of lowercase English letters.
All the strings of req_skills are unique.
1 <= people.length <= 60
0 <= people[i].length <= 16
1 <= people[i][j].length <= 16
people[i][j] consists of lowercase English letters.
All the strings of people[i] are unique.
Every skill in people[i] is a skill in req_skills.
It is guaranteed a sufficient team exists.

Example 1:

**Input:** req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"|"java"],["nodejs"],["nodejs","reactjs"]]
**Output:** [0,2]

Solve¶

Input handling¶

With the provided constrain for input, we can turn input to it’s bit representation.

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        words_dictinary = req_skills.copy()
        words_dictinary.sort()
        number_representation = []
        for p in people:
            craft_number = 0
            for skill in p:
                words_index = bisect_right(words_dictinary, skill) - 1
                craft_number += 1 << words_index
            number_representation.append(craft_number)

I debug above code using these to make sure it done right:

print (words_dictinary)
for i in number_representation:
    print (bin(i + (1 << len(words_dictinary)))[3:] )

First commit: Brute force¶

We try all possible combination way of choosing people. Which start from 000..00 -> 1111..11 (bit length equal total people)

Every 1 bit mean we choosing the people in that bit index to the team (which we create a helper function to loop through bit_1_pos)
To check our choosing team is sufficient, We can use or operator | on all skill of chosen people number_representation[index]. If final result return 111..11 on all req_skills skill (bit length equal total required skill).

Why? Because we only need one people in the team have the correspond req_skills, which equivalent to or operation,

Using utility function bit_count to keep track of how many 1 bit in the number to help checking/ backtracking worse solution (any total team with is have higher people). Final code:

Here is where I realize read the question wrong, my first thought is that len(people) < 2**16, which make me thing for loop 2**16 is a good ideal. This code bellow is trash with possible 2**60 case

class Solution:
    def bit_1_pos(self, number):
        for pos, c in enumerate`-1]`:
            if c == '1':
                yield pos

    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        words_dictinary = req_skills.copy()
        words_dictinary.sort()
        number_representation = []
        for p in people:
            craft_number = 0
            for skill in p:
                words_index = bisect_right(words_dictinary, skill) - 1
                craft_number += 1 << words_index
            number_representation.append(craft_number)

        start = 0
        last = (1<<len(people)) -1

        best = last
        for possible_combination in range(start, last):
            is_sufficient = 0
            if possible_combination.bit_count() > best.bit_count():
                continue

            for index in self.bit_1_pos(possible_combination):
                is_sufficient = is_sufficient | number_representation[index] # or operation

            if is_sufficient.bit_count() == len(words_dictinary):
                best = possible_combination

        return [i for i in self.bit_1_pos(best)]

Update the backtracking¶

possible_combination <= 2**60 , which is too large. So I implement a queue to keep the track going on the right direction. Where at least a new skill in push into team with each people added.

Time Submitted	Status	Runtime	Memory	Language
07/16/2023 21:02	Time Limit Exceeded	N/A	N/A	python3

class Solution:
    def bit_1_pos(self, number):
        for pos, c in enumerate`-1]`:
            if c == '1':
                yield pos

    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        words_dictinary = req_skills.copy()
        words_dictinary.sort()
        number_representation = []
        for p in people:
            craft_number = 0
            for skill in p:
                words_index = bisect_right(words_dictinary, skill) - 1
                craft_number += 1 << words_index
            number_representation.append(craft_number)

        start = 0
        last = (1 << len(people)) - 1

        best = last
        queue = [(start, 0)]
        visited = set()
        while len(queue) > 0:
            possible_combination, is_sufficient = queue.pop(0)
            visited.add(possible_combination)
            if possible_combination.bit_count() > best.bit_count():
                continue

            if is_sufficient.bit_count() == len(words_dictinary):
                best = possible_combination
                break

            for index in range(len(people)):
                team_skill = is_sufficient | number_representation[index]
                if team_skill == is_sufficient:
                    continue
                team_member = possible_combination | (1 << index)
                if team_member in visited:
                    continue
                visited.add(team_member)
                queue.append((team_member, team_skill))

        return [i for i in self.bit_1_pos(best)]

(Yank) Dynamic programing¶

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str],
                               people: List[List[str]]) -> List[int]:
        n = len(people)
        m = len(req_skills)
        skill_id = dict()
        for i, skill in enumerate(req_skills):
            skill_id[skill] = i
        skills_mask_of_person = [0] * n
        for i in range(n):
            for skill in people[i]:
                skills_mask_of_person[i] |= 1 << skill_id[skill]
        dp = [(1 << n) - 1] * (1 << m)
        dp[0] = 0
        for skills_mask in range(1, 1 << m):
            for i in range(n):
                smaller_skills_mask = skills_mask & ~skills_mask_of_person[i]
                if smaller_skills_mask != skills_mask:
                    people_mask = dp[smaller_skills_mask] | (1 << i)
                    if people_mask.bit_count() < dp[skills_mask].bit_count():
                        dp[skills_mask] = people_mask

        answer_mask = dp[(1 << m) - 1]
        ans = []
        for i in range(n):
            if (answer_mask >> i) & 1:
                ans.append(i)
        return ans

Bit mark, understandable, skills_mask_of_person is the same as number_representation representation of my previous approach. While to use Dynamic programing, here should be the explanation:

start an array dp with a length of 2**len(req_skill) and default value 2**len(people) - 1. Which answer question given a needed set req_skill in binary representation, how to chose the minimal teem people possible, also in in binary representation. The worst default oblivious that choosing all people.
dp[0] = 0, so no one needed to if there is no req_skill.

With every possible combination require skills_mask set of skill start from 000..00 to 111..11 (length of require skill with the maximum of 2**16), update current skills_mask set dp by trying with each person (range from [0..n]):

find a previous_skills_mask that when adding person[i] skill set (which mean adding skills_mask_of_person[i] to previous_skills_mask we can qualify all skill in skill_masks)

after that, try update dp[skill_masks] = dp[previous_skills_mask] add person[i] if it a better team (with lower people)

        dp = [(1 << n) - 1] * (1 << m)
        dp[0] = 0
        for skills_mask in range(1, 1 << m):
            for i in range(n):
                smaller_skills_mask = skills_mask & ~skills_mask_of_person[i]
                if smaller_skills_mask != skills_mask:
                    people_mask = dp[smaller_skills_mask] | (1 << i)
                    if people_mask.bit_count() < dp[skills_mask].bit_count():
                        dp[skills_mask] = people_mask

        answer_mask = dp[(1 << m) - 1]
        ans = []
        for i in range(n):
            if (answer_mask >> i) & 1:
                ans.append(i)

Update to Dynamic programing¶

Knowing the ideal, here is my re implementation using similar dp approach. Which on my first try isn’t that fast, because of the commended for loop shown here

        for needed_skills, curr_best in enumerate(best_team):
            for index, skill_set in enumerate(number_representation):
                # team_knowed_skill_set = needed_skills
                # for pos in self.bit_1_pos(skill_set):
                #    team_knowed_skill_set = team_knowed_skill_set & ~(1 << pos)

                team_knowed_skill_set = needed_skills & ~skill_set

Time Submitted	Status	Runtime	Memory	Language	Agro
07/16/2023 12:50	Accepted	8519 ms	18.8 MB	python3	Unoptimal
07/16/2023 21:37	Accepted	1650 ms	18.9 MB	python3	Remove the for loop

class Solution:
    def bit_1_pos(self, number):
        for pos, c in enumerate`-1]`:
            if c == '1':
                yield pos

    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        words_dictinary = req_skills.copy()
        words_dictinary.sort()
        number_representation = []
        for p in people:
            craft_number = 0
            for skill in p:
                words_index = bisect_right(words_dictinary, skill) - 1
                craft_number += 1 << words_index
            number_representation.append(craft_number)

        all_people = (1<<len(people)) -1

        best_team = [all_people] * (1 << len(req_skills))
        best_team[0] = 0
        for needed_skills, curr_best in enumerate(best_team):
            for index, skill_set in enumerate(number_representation):
                team_knowed_skill_set = needed_skills & ~skill_set
                knowed_best_team = best_team[team_knowed_skill_set]
                if best_team[needed_skills].bit_count() > knowed_best_team.bit_count() +1:
                    best_team[needed_skills] = knowed_best_team | (1 << index)

        return [i for i in self.bit_1_pos(best_team[-1])]

Best. Greedy all the way from top¶

This is a very clear code with showing exactly the intention from code alone.

Each time you want to choosing a people. Choose all have the most rare skill and push them in to queue, keeping track of remaining skill and curr_group
Overall a nice implementation of a BFS with a set of wise define rule.

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skill_possessor_lookup = [set() for _ in req_skills]
        skill_ID_lookup = {skill: pos for pos, skill in enumerate(req_skills)}

        for person_id, person in enumerate(people):
            for skill in person:
                skill_ID = skill_ID_lookup[skill]
                skill_possessor_lookup[skill_ID].add(person_id)

        queue = deque([(skill_possessor_lookup, [])])

        while queue:
            top_skills, curr_group = queue.popleft()
            rarest_skill_possessors = min(top_skills, key=len)
            for person_id in rarest_skill_possessors:
                remaining_skills = [possessor for possessor in top_skills if person_id not in possessor]
                if not remaining_skills:
                    return curr_group + [person_id]
                queue.append((remaining_skills, curr_group + [person_id]))

Here is my implementation it again. Here is some take away:

In our first try of burst force backtracking, we only find person that provide some thing to the team (adding at least one more skill). This isn’t enough as we still need to go through many cases.
This is where the rarest skill is introduce, adding another this layer of backtrack/greedy. Minimizing the multiple of branch that we need to check on each loop.
This implementation showing that a powerful backtracking give a lot of credit on performance of the code.

class Solution:
    def find_rarest_skill(self, candidates, skill_set, not_needed_skill):
        skill_talent = {}
        for candidate in candidates:
            for skill in skill_set[candidate]:
                if skill not in skill_talent:
                    skill_talent[skill] = set()
                skill_talent[skill].add(candidate)

        rarest_skill = None

        for skill in skill_talent:
            if skill in not_needed_skill:
                continue
            if rarest_skill is None:
                rarest_skill = skill
            elif len(skill_talent[rarest_skill]) > len(skill_talent[skill]):
                rarest_skill = skill

        return rarest_skill, skill_talent[rarest_skill]

    def smallestSufficientTeam(self, req_skills: List[str],
                               people: List[List[str]]) -> List[int]:
        queue = [(set(range(len(people))), set())]
        while queue:
            available_people, current_team_skill = queue.pop(0)
            if available_people is None:
                return [i for i in len(people)]
            if len(current_team_skill) == len(req_skills):
                return list(set(range(len(people))).difference(available_people))

            _, talented_peoples = self.find_rarest_skill(
                available_people, people, current_team_skill)

            for candidate in talented_peoples:
                team_skill = current_team_skill.union(set(people[candidate]))
                remain_people = available_people.copy().remove(candidate)
                queue.append((remain_people, team_skill))
                if len(team_skill) == len(req_skills):
                    queue = [queue[-1]]
                    break

        return [i for i in len(people)]

Reimplement my Backtracking code again. Here I not try to find a rarest skill, just chose a not found skill (sub optimal). The final result is way greater nonetheless even comparing to Dynamic programming option

Time Submitted	Status	Runtime	Memory	Language	Argo
07/16/2023 23:06	Accepted	200 ms	23.3 MB	python3	Rewirte Backtrack
07/16/2023 20:38	Accepted	61 ms	16.6 MB	python3	Rewrite queue

class Solution:
    def bit_1_pos(self, number):
        for pos, c in enumerate`-1]`:
            if c == '1':
                yield pos

    def needed_skill(self, number):
        tmp = number
        pos = 0
        while tmp != 0:
            if tmp % 2 == 1:
                tmp = tmp // 2
                pos += 1
            else:
                break
        return pos

    def smallestSufficientTeam(self, req_skills: List[str],
                               people: List[List[str]]) -> List[int]:
        words_dictinary = req_skills.copy()
        words_dictinary.sort()
        number_representation = []
        for p in people:
            craft_number = 0
            for skill in p:
                words_index = bisect_right(words_dictinary, skill) - 1
                craft_number += 1 << words_index
            number_representation.append(craft_number)

        start = 0
        last = (1 << len(people)) - 1

        best = last
        queue = [(start, 0)]
        visited = set()
        while len(queue) > 0:
            possible_combination, is_sufficient = queue.pop(0)
            visited.add(possible_combination)
            if possible_combination.bit_count() > best.bit_count():
                continue

            if is_sufficient.bit_count() == len(words_dictinary):
                best = possible_combination
                break

            needed_skill = self.needed_skill(is_sufficient)
            for index in range(len(people)):
                if (number_representation[index] >> needed_skill) % 2 == 0:
                    continue
                team_skill = is_sufficient | number_representation[index]
                if team_skill == is_sufficient:
                    continue
                team_member = possible_combination | (1 << index)
                if team_member in visited:
                    continue
                visited.add(team_member)
                queue.append((team_member, team_skill))

        return [i for i in self.bit_1_pos(best)]

Last update : October 13, 2023
Created : August 16, 2023