23.07.16 Today’s Leetcode

1125. Smallest Sufficient Team

Greedy Approach

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        arr = [(value, i) for i, value in enumerate(people)]
        arr.sort(key= lambda x: -len(x[0]))
        print(arr)

        req = set(req_skills)
        res = []
        while req:
            lar = set()
            index = -1
            for skill, i in arr:
                temp = set(skill) & req 
                if len(temp) >= len(lar):
                    lar = temp
                    index = i
                
            print(lar)
            req -= lar
            res.append(index)

        return res

DFS Approach

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        arr = [(set(value), i) for i, value in enumerate(people)]
        arr.sort(key= lambda x: -len(x[0]))
        n = len(arr)
        # print(arr)

        req = set(req_skills)
        res = [0] * n
        recruit = []

        # @functools.lru_cache(None)
        def dfs(cur_req, index):
            nonlocal res, recruit
            # print(recruit, cur_req, index)
            if not cur_req:
                if len(recruit) < len(res):
                    res = recruit[:]
                return
            if len(recruit) >= len(res):
                return
            if index >= n:
                return

            for i in range(index, n):
                cur_skill, cur_index = arr[i]
                recruit.append(cur_index)
                dfs(cur_req - cur_skill, i + 1)
                recruit.pop()

        dfs(req, 0)
        return res

Bit manipulation

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        m = len(req_skills)
        n = len(people)
        skill_index = {v: i for i, v in enumerate(req_skills)}
        cand = []
        for skills in people:
            val = 0
            for skill in skills:
                val |= 1 << skill_index[skill]

            cand.append(val)

        @cache
        def fn(i, mask):
            if mask == 0:
                return []
            if i == n:
                return [0] * 100
            if not (mask & cand[i]):
                return fn(i + 1, mask)
            return min(fn(i + 1, mask), [i] + fn(i + 1, mask & ~cand[i]), key=len)

        return fn(0, (1 << m) - 1)