What the complexity of this algorithm is? I want to express the complexity of big-O. I don't know for the life of me.
Problem: req_skill : list of required skills people : 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.
Example 1: Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]] Output: [0,2]
Solution:
class Solution:
def smallestSufficientTeam(self, skills: List[str], people: List[List[str]]) -> List[int]:
# Contains a set with each person containing the skill in the skill
skill_list: List[Set[str]] = [set() for _ in skills]
# Map w/ skill to index (to fill skill_list easier)
skill_map: Dict[str, int] = {skill: i for i, skill in enumerate(skills)}
# Fills skill_list with index of skill containing person having skill
for i, person in enumerate(people):
for skill in person:
skill_list[skill_map[skill]].add(i)
# Queue for bfs. Passing in skill_list and current chosen people
queue: List[Tuple[List[Set[str]], List[int]]] = []
queue.append((skill_list, []))
while queue != []:
top_skill_set, top_people = queue.pop(0)
# Picks skill w/ smallest number of people involved, and
for person in list(min(top_skill_set, key=len)):
# Eliminates all skills that "person" has
new_skill_list = [skill for skill in top_skill_set
if person not in skill]
if new_skill_list == []:
# If no more skills left, this is shortest group yet
# Note: Because this is a BFS, this will always be shortest
return top_people + [person]
else:
# Add new_skill_list to queue
queue.append((new_skill_list, top_people + [person]))
return [] # If no solution exists, return empty array
question: https://leetcode.com/problems/smallest-sufficient-team/ code : https://leetcode.com/problems/smallest-sufficient-team/discuss/1402490/Python-Solution-(24ms-beating-100)
thank you very much.