ধরুন আমাদের কাছে একই আকারের দুটি তালিকা রয়েছে, এগুলি হল সময়সীমা এবং ক্রেডিট এবং তারা কোর্স অ্যাসাইনমেন্টের প্রতিনিধিত্ব করছে। এখানে ডেডলাইন[i] অ্যাসাইনমেন্ট i এর জন্য ডেডলাইন দিন দেখায় এবং ক্রেডিট[i] অ্যাসাইনমেন্টের জন্য আমরা যে পরিমাণ ক্রেডিট পাই তা প্রতিনিধিত্ব করে। আমাদের কাছে একটি অ্যাসাইনমেন্ট সম্পূর্ণ করার জন্য একদিন আছে, এবং সময়সীমার দিন আগে বা শেষ করা যেতে পারে। আমরা একই সময়ে একাধিক অ্যাসাইনমেন্ট করতে পারি না। কিছু সাবসেট অ্যাসাইনমেন্ট শেষ করে আমাদের সর্বাধিক ক্রেডিট পেতে হবে।
সুতরাং, যদি ইনপুট সময়সীমার মত হয় =[1, 2, 2, 2] ক্রেডিট =[4, 5, 6, 7], তাহলে আউটপুট হবে 18, যেহেতু আমরা ক্রেডিট 5 দিয়ে অ্যাসাইনমেন্ট সম্পূর্ণ করতে পারি 0 দিনে, সম্পূর্ণ প্রথম দিনে ক্রেডিট 6 সহ অ্যাসাইনমেন্ট এবং তৃতীয় দিনে 7 ক্রেডিট সহ সম্পূর্ণ অ্যাসাইনমেন্ট৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- a :=সময়সীমা এবং ক্রেডিটগুলির একটি জোড়া তৈরি করুন এবং ক্রেডিটগুলির উপর ভিত্তি করে সাজানো ক্রমে সাজান
- যদি a খালি হয়, তাহলে
- রিটার্ন 0
- res :=আকারের একটি তালিকা (1 + সর্বোচ্চ সময়সীমা) এবং 0 দিয়ে পূরণ করুন
- উত্তর :=0
- এ প্রতিটি জোড়ার জন্য (i, j) a, do
- রেঞ্জের k-এর জন্য i 0 থেকে কম, 1 দ্বারা হ্রাস করুন,
- করুন
- যদি res[k] 0 হয়, তাহলে
- res[k] :=1
- উত্তর :=ans + j
- লুপ থেকে বেরিয়ে আসুন
- যদি res[k] 0 হয়, তাহলে
- রেঞ্জের k-এর জন্য i 0 থেকে কম, 1 দ্বারা হ্রাস করুন,
- উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution: def solve(self, deadlines, credits): a = sorted(list(zip(deadlines, credits)), key=lambda x: x[1], reverse=True) if not a: return 0 res = [0] * (max(deadlines) + 1) ans = 0 for i, j in a: for k in range(i, -1, -1): if not res[k]: res[k] = 1 ans += j break return ans ob = Solution() deadlines = [1, 2, 2, 2] credits = [4, 5, 6, 7] print(ob.solve(deadlines, credits))
ইনপুট
[1, 2, 2, 2], [4, 5, 6, 7]
আউটপুট
18