Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出需要的skill list和每个人的skill,问最少需要其中的几个人可以满足skill list里面所有skill
二进制表示skill+DP,参考Discussion -> https://leetcode.com/problems/smallest-sufficient-team/solutions/3771208/detailed-video-solution-java-python/


#1125
#
Runtime: 121 ms (Beats 88.89%)
#
Memory: 18.1 MB (Beats 44.44%)

class Solution(object):
    def smallestSufficientTeam(self, req_skills, people):
        """
        :type req_skills: List[str]
        :type people: List[List[str]]
        :rtype: List[int]
        
"""
        n_p = len(people)
        n_s = len(req_skills)
        sk_map = {sk: i for i, sk in enumerate(req_skills)}
        dp = [None] * (1 << n_s)
        dp[0] = []
        sk_p = []
        for i in range(n_p):
            t = 0
            for sk in people[i]:
                t |= 1 << sk_map[sk]
            sk_p.append(t)
        discard_p = [False] * n_p
        for i in range(n_p):
            for j in range(i + 1, n_p):
                if (sk_p[j] | sk_p[i]) == sk_p[i]:
                    discard_p[j] = True
                elif (sk_p[j] | sk_p[i]) == sk_p[j]:
                    discard_p[i] = True
        for i in range(n_p):
            if not discard_p[i]:
                for j in range(len(dp)):
                    if dp[j] is None:
                        continue
                    t = j | sk_p[i]
                    if dp[t] is None or len(dp[j]) + 1 < len(dp[t]):
                        dp[t] = dp[j] + [i]
        return dp[(1 << n_s) - 1]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理