कुछ असाइनमेंट पूरा करके प्राप्त होने वाले अधिकतम क्रेडिट ज्ञात करने का पायथन प्रोग्राम

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

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

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

• 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