পাইথনে কিছু অ্যাসাইনমেন্ট সম্পন্ন করে সর্বোচ্চ ক্রেডিট পাওয়ার প্রোগ্রাম

मान लीजिए हमारे पास एक ही आकार की दो सूचियाँ हैं, ये हैं डेडलाइन्स और क्रेडिट्स और ये कोर्स असाइनमेंट्स को दर्शाती हैं। यहाँ deadlines[i] असाइनमेंट i के लिए अंतिम दिन दिखाता है और credits[i] असाइनमेंट i के लिए मिलने वाले क्रेडिट की मात्रा दर्शाता है। हमारे पास एक असाइनमेंट पूरा करने के लिए एक दिन है, और इसे डेडलाइन के दिन या उससे पहले पूरा किया जा सकता है। हम एक ही समय में कई असाइनमेंट नहीं कर सकते। हमें कुछ सबसेट असाइनमेंट्स खत्म करके अधिकतम क्रेडिट ढूंढना है।

तो, अगर इनपुट डेडलाइन्स = [1, 2, 2, 2] क्रेडिट्स = [4, 5, 6, 7] है, तो आउटपुट 18 होगा, क्योंकि हम क्रेडिट 5 वाला असाइनमेंट दिन 0 पर, क्रेडिट 6 वाला दिन 1 पर और क्रेडिट 7 वाला दिन 3 पर पूरा कर सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• a := डेडलाइन्स और क्रेडिट्स का जोड़ा बनाएं और उन्हें क्रेडिट के आधार पर अवरोही क्रम में सॉर्ट करें
• अगर a खाली है, तो
  • 0 लौटाएं
• res := (डेडलाइन्स के अधिकतम + 1) आकार की सूची और 0 से भरें
• ans := 0
• प्रत्येक जोड़ी (i, j) के लिए a में, करें
  • k को i से 0 तक घटाते हुए, करें
    • अगर res[k] 0 है, तो
      • res[k] := 1
      • ans := ans + j
      • लूप से बाहर आएं
• ans लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

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