पायथन में जॉब शेड्यूलिंग से अधिकतम लाभ प्राप्त करने का प्रोग्राम

मान लीजिए हमारे पास अंतराल की एक लिस्ट है जहां प्रत्येक अंतराल में तीन मान [start, end, profit] होते हैं। हम एक समय में केवल एक कार्य कर सकते हैं, हमें अधिकतम लाभ ढूंढना है जो हम प्राप्त कर सकते हैं।

उदाहरण के लिए, यदि इनपुट intervals = [[1, 2, 100], [3, 5, 40], [6, 19, 150], [2, 100, 250]] है, तो आउटपुट 350 होगा, क्योंकि हम ये दो अंतराल ले सकते हैं: [1, 2, 100] और [2, 100, 250]।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे:

d := एक खाली मैप जिसमें लिस्ट वैल्यू हों
n := 0
प्रत्येक (start, end, profit) के लिए intervals में:
- यदि end > n है, तो n := end
- (start, profit) पेयर को d[end] में डालें
A := आकार n + 1 की लिस्ट, 0 से भरी हुई
end को 0 से A के आकार - 1 तक लूप चलाएं:
- यदि end, d में है:
  - प्रत्येक (start, profit) पेयर के लिए d[end] में:
    - A[end] := max(A[end], A[start] + profit, A[end - 1])
- अन्यथा, A[end] := A[end - 1]
A का अंतिम मान लौटाएं

पायथन कार्यान्वयन

from collections import defaultdict

class Solution:
    def solve(self, intervals):
        d = defaultdict(list)
        n = 0
        for start, end, profit in intervals:
            if end > n:
                n = end
            d[end].append([start, profit])
        A = [0 for i in range(n + 1)]
        for end in range(len(A)):
            if end in d:
                for start, profit in d[end]:
                    A[end] = max(A[end], A[start] + profit, A[end - 1])
            else:
                A[end] = A[end - 1]
        return A[-1]

ob = Solution()
intervals = [[1, 2, 100], [3, 5, 40], [6, 19, 150], [2, 100, 250]]
print(ob.solve(intervals))

इनपुट

[[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]