পাইহটনের সবচেয়ে ছোট পর্যাপ্ত দল

ধরুন একটি প্রকল্পের জন্য আমাদের কাছে প্রয়োজনীয় দক্ষতার একটি তালিকা রয়েছে যাকে বলা হয় req_skills, এবং মানুষের একটি তালিকা। এখানে i-th people people[i] ব্যক্তির দক্ষতার একটি তালিকা রয়েছে।

এখন ধরুন একটি পর্যাপ্ত দলকে লোকদের একটি সেট হিসাবে সংজ্ঞায়িত করা হয়েছে যেমন req_skills-এ প্রতিটি প্রয়োজনীয় দক্ষতার জন্য, দলে কমপক্ষে একজন ব্যক্তি রয়েছে যার সেই দক্ষতা রয়েছে। আমরা প্রতিটি ব্যক্তির সূচী দ্বারা এই দলগুলিকে প্রতিনিধিত্ব করতে পারি:উদাহরণ হিসাবে ধরুন দল হল [0, 1, 3] এটি দক্ষতাসম্পন্ন লোকদের প্রতিনিধিত্ব করে[0], মানুষ[1], এবং লোক[3]।

আমাদের সবচেয়ে ছোট সম্ভাব্য আকারের দল খুঁজে বের করতে হবে।

আপনি যেকোনো ক্রমে উত্তর ফেরত দিতে পারেন। এটা নিশ্চিত যে একটি উত্তর বিদ্যমান।

সুতরাং, যদি ইনপুট হয় req_skills =["java","flutter","android"], people =[["java"],["android"],["flutter","android"]], তাহলে আউটপুট হবে [0,2]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• dp :=একটি মানচিত্র, কী 0

  এর সাথে সম্পর্কিত খালি তালিকা যোগ করুন

• key :=একটি মানচিত্র যেমন (মান,i) যেখানে মান req_skills থেকে এবং i হল সংখ্যা

• সংখ্যার জন্য, লোকের অ্যারে থেকে ব্যক্তি জোড়া (i, p) লোক নিয়ে তাদের নম্বর বরাদ্দ করুন -

  • বর্তমান_দক্ষতা :=0

  • p

    এ দক্ষতার জন্য

    • বর্তমান_দক্ষতা :=বর্তমান_দক্ষতা বা 2^কী[স্কিল]

  • (দক্ষতা_সেট,সদস্যদের) জোড়াটি dp কী-মান জোড়ায় থাকে −

    • মোট_দক্ষতা :=দক্ষতা_সেট বা বর্তমান_দক্ষতা

    • যদি মোট_দক্ষতা দক্ষতা_সেটের সমান হয়, তাহলে −

      • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

    • যদি টোটাল_স্কিল ডুতে না থাকে বা 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]