ধরুন আমাদের কাছে টাস্ক নামক পূর্ণসংখ্যার একটি তালিকা আছে যেখানে প্রতিটি আইটেম একটি ভিন্ন টাস্ক টাইপের প্রতিনিধিত্ব করে, আমাদের কাছে একটি অ-ঋণাত্মক পূর্ণসংখ্যাও আছে যেমন k বলে। প্রতিটি কাজ সম্পূর্ণ হতে এক একক সময় নেয় এবং কাজগুলিকে অবশ্যই সঠিক ক্রমে সম্পন্ন করতে হবে, তবে আমাদের অবশ্যই দুটি একই ধরণের কাজ করার মধ্যে সময়ের k একক থাকতে হবে। যে কোনো সময়, হয় আমরা একটি কাজ করতে পারি বা অপেক্ষা করতে পারি। সমস্ত কাজ সম্পূর্ণ করতে আমাদের কতটা সময় লাগে তা খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট টাস্কস =[0, 1, 1, 2] k =2 এর মত হয়, তাহলে আউটপুট হবে 6, কারণ প্রথম দুটি টাস্ক ভিন্ন ধরনের, তাই সেগুলিকে কোনো ফাঁক ছাড়াই চালানো যায়, এখন সময়ে 2, পরবর্তী কাজটি একই ধরণের টাস্কের জন্য আমাদের 2-টাইম স্লটের জন্য অপেক্ষা করতে হবে, তারপর টাস্কটি করতে হবে এবং অবশেষে অন্য টাইপ টাস্ক আছে, 2 টাইপ করুন। তাই এই কাজটি করুন। সুতরাং এটি [0, 1, অপেক্ষা করুন, অপেক্ষা করুন, 1, 2]। এটি থেকে আমরা সনাক্ত করতে পারি, আমাদের 6টি টাইম স্লট দরকার।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- টিক করুন :=0
- স্লট :=একটি নতুন মানচিত্র
- প্রতিটি কাজের জন্য, করুন
- tf :=slot[t] যদি t স্লটে থাকে
- যদি tf নাল না হয় এবং tf - টিক> 0, তারপর
- টিক :=টিক + tf - টিক
- টিক :=টিক + 1
- slot[t] :=টিক + k
- রিটার্ন টিক
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(tasks, k):
tick = 0
slot = {}
for t in tasks:
tf = slot.get(t)
if tf is not None and tf - tick > 0:
tick += tf - tick
tick += 1
slot[t] = tick + k
return tick
tasks = [0, 1, 1, 2]
k = 2
print(solve(tasks, k)) ইনপুট
[0, 1, 1, 2]
আউটপুট
6
