সমস্যা বিবরণ
প্রজেক্টের জন্য প্রয়োজনীয় স্কিলের লিস্ট req_skills এবং মানুষের লিস্ট people (প্রতিটি ব্যক্তির স্কিল লিস্ট) দেওয়া থাকে। সব রিকোয়ার্ড স্কিল কভার করে এমন সবচেয়ে ছোট টিম (ইন্ডেক্স লিস্ট) বের করুন।
উদাহরণ
req_skills = ["java","flutter","android"], people = [["java"],["android"],["flutter","android"]] → আউটপুট: [0,2]
ব্যক্তি ০ (java) + ব্যক্তি ২ (flutter, android) = সব স্কিল কভার।
এলগরিদম (Bitmask DP)
- প্রতিটি স্কিলকে একটি বিট পজিশনে ম্যাপ করুন:
skill -> bit index। dp[mask] = team_indices—maskস্কিল সেট অর্জন করতে ন্যূনতম টিম।dp[0] = []দিয়ে শুরু।- প্রতিটি ব্যক্তি
iএর জন্য:- তাঁর স্কিল থেকে
cur_maskবানান। - বিদ্যমান সব
maskএর সাথেnew_mask = mask | cur_maskকরুন। - যদি
new_maskএখনও নেই বা ছোট টিম দিয়ে সম্ভব →dp[new_mask] = dp[mask] + [i]।
- তাঁর স্কিল থেকে
dp[(1<
পাইথন বাস্তবায়ন
class Solution:
def smallestSufficientTeam(self, req_skills, people):
dp = {0: []}
skill_index = {v: i for i, v in enumerate(req_skills)}
for i, p in enumerate(people):
cur_skill = 0
for skill in p:
cur_skill |= 1 << skill_index[skill]
for mask, team in list(dp.items()):
new_mask = mask | cur_skill
if new_mask == mask:
continue
if new_mask not in dp or len(dp[new_mask]) > len(team) + 1:
dp[new_mask] = team + [i]
return dp[(1 << len(req_skills)) - 1]
ob = Solution()
print(ob.smallestSufficientTeam(["java","flutter","android"],
[["java"],["android"],["flutter","android"]])) # [0, 2]ইনপুট / আউটপুট
ইনপুট: ["java","flutter","android"], [["java"],["android"],["flutter","android"]] আউটপুট: [0, 2]
