পাইথনে টাস্ক শিডিউলিং করে ন্যূনতম সময়ে সম্পন্ন করা (Cooldown কনস্ট্রেইন্ট)

দেওয়া টাস্ক লিস্ট nums (প্রতিটি ভ্যালু আলাদা টাস্ক টাইপ) এবং কুলডাউন k। প্রতিটি টাস্ক ১ মিনিট নেয়, কিন্তু একই টাইপের দুটি টাস্কের মাঝপথে কমপক্ষে k মিনিট গ্যাপ থাকতে হবে। ন্যূনতম টোটাল টাইম বের করতে হবে।

উদাহরণ: nums=[2,2,2,3,3,2], k=1 → অপ্টিমাল অর্ডার: [2,3,2,3,2,WAIT,2] → আউটপুট 7।

গ্রিডি + কাউন্টার সমাধান

1. Counter দিয়ে ফ্রিকোয়েন্সি গণনা।
2. যতক্ষন কাউন্টার খালি নয়:
   • সর্বোচ্চ ফ্রিকোয়েন্সি वाले k+1 টাস্ক নিন।
   • প্রতিটির কাউন্ট ১ কমান, ০ হলে মুছে দিন।
   • ans += k+1।
3. ফাইনাল আন্ডারস্টিমেশন: ans + last_size - (k+1)।

পাইথন কোড

from collections import Counter

class Solution:
    def solve(self, nums, k):
        c = Counter(nums)
        ans = 0
        lastsize = 0
        while c:
            lastsize = len(c)
            for x, _ in c.most_common(k + 1):
                c[x] -= 1
                if c[x] == 0:
                    del c[x]
            ans += k + 1
        return ans + lastsize - (k + 1)

ob1 = Solution()
print(ob1.solve([2, 2, 2, 3, 3, 2], 1))  # 7

টাইম কমপ্লেক্সিটি: O(n log m) (m = ইউনিক টাস্ক টাইপ), স্পেস: O(m)। এটি লিটকোড "Task Scheduler" সমস্যার সমাধান।