पायथन में सबसे छोटी पर्याप्त टीम

मान लीजिए एक परियोजना के लिए हमारे पास req_skills नामक आवश्यक कौशल की सूची है, और लोगों की एक सूची है। यहां i-वें लोग people[i] में उस व्यक्ति के कौशल की सूची होती है।

अब मान लीजिए एक पर्याप्त टीम को लोगों के एक समूह के रूप में परिभाषित किया गया है जैसे कि req_skills में हर आवश्यक कौशल के लिए, टीम में कम से कम एक व्यक्ति हो जिसके पास वह कौशल हो। हम इन टीमों को प्रत्येक व्यक्ति के सूचकांक द्वारा दर्शा सकते हैं: उदाहरण के लिए मान लीजिए टीम [0, 1, 3] है जो people[0], people[1], और people[3] के कौशल वाले लोगों को दर्शाती है।

हमें सबसे छोटे संभव आकार की टीम ढूंढनी है।

आप किसी भी क्रम में उत्तर वापस कर सकते हैं। यह गारंटी है कि एक उत्तर मौजूद है।

उदाहरण के लिए, यदि इनपुट req_skills = ["java","flutter","android"], people = [["java"],["android"],["flutter","android"]] है, तो आउटपुट [0,2] होगा।

हल करने के चरण

dp := एक मैप, खाली सूची को कुंजी 0 से जोड़ें
key := (value,i) जैसा मैप जहां value req_skills से है और i संख्याएं हैं
लोगों की सरणी से (i, p) संख्या, व्यक्ति जोड़ी के लिए people लेकर उन्हें संख्या निर्दिष्ट करके:
- current_skill := 0
- p में कौशल के लिए:
  - current_skill := current_skill OR 2^key[skill]
- dp की कुंजी-मान जोड़ी (skill_set, members) के लिए:
  - total_skill := skill_set OR current_skill
  - यदि total_skill, skill_set के बराबर है, तो:
    - निम्न भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
  - यदि total_skill dp में नहीं है या dp[total_skill] का आकार > members का आकार + 1, तो:
    - dp[total_skill] := members + [i]
dp[(1 << len(req_skills)) - 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]