Pyhtonで最小の十分なチーム

プロジェクトに、req_skillsと呼ばれる必要なスキルのリストと人のリストがあるとします。ここで、i番目の人[i]には、その人が持っているスキルのリストが含まれています。

ここで、十分なチームが、req_skillsで必要なスキルごとに、そのスキルを持っているチームに少なくとも1人の人がいるような一連の人として定義されているとします。これらのチームは、各人のインデックスで表すことができます。たとえば、チームが[0、1、3]であるとすると、これはスキルを持つ人[0]、人[1]、人[3]を表します。

可能な限り最小のサイズのチームを見つける必要があります。

回答は任意の順序で返すことができます。答えが存在することが保証されています。

したがって、入力がreq_skills =["java"、 "flutter"、 "android"]のようである場合、people =[["java"]、["android"]、["flutter"、 "android"]]、出力は[0,2]

これを解決するには、次の手順に従います-

• dp：=1つのマップ、キー0に対応する空のリストを追加

• key：=（value、i）のようなマップ。ここで、valueはreq_skillsからのものであり、iは数値です

• 番号の場合、人を取得して番号を割り当てることにより、人の配列からの人のペア（i、p）-

  • current_skill：=0

  • pのスキルのために

    • current_skill：=current_skillまたは2^ key [skill]

  • for（skill_set、members）pair is in dp key-value pair-

    • total_skill：=skill_setまたはcurrent_skill

    • total_skillがskill_setと同じ場合、-

      • 次の部分を無視し、次の反復にスキップします

    • total_skillがdoまたはdp[total_skill]のサイズ>メンバーのサイズ+1でない場合、

      • dp [total_skill]：=メンバー+ [i]

• dp [（1 <を返します

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def smallestSufficientTeam(self, req_skills, people):
      dp = {0:[]}
      key = {v:i for i,v in enumerate(req_skills)}
      for i,p in enumerate(people):
         current_skill = 0
         for skill in p:
         current_skill |= 1<< key[skill]
      for skill_set, members in dp.items():
         total_skill = skill_set|current_skill
         if total_skill == skill_set:
            continue
         if total_skill not in dp or len(dp[total_skill])>
len(members)+1:
            dp[total_skill] = members + [i]
      return dp[(1<<len(req_skills)) - 1]
ob = Solution()
print(ob.smallestSufficientTeam(["java","flutter","android"],
[["java"],["android"],["flutter","android"]]))

入力

["java","flutter","android"]
[["java"],["android"],["flutter","android"]]

出力

[0,2]