पायथन में नौकरियों को शेड्यूल करके अधिकतम लाभ प्राप्त करने का कार्यक्रम

मान लीजिए कि हमारे पास अंतराल की एक सूची है जहां प्रत्येक अंतराल में तीन मान होते हैं [प्रारंभ, अंत, लाभ]। हम एक समय में केवल एक ही कार्य कर सकते हैं, हमें जितना अधिक लाभ प्राप्त हो सकता है, उसे खोजना होगा।

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

. को ले सकते हैं

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

d :=एक खाली नक्शा जिसमें मान के रूप में सूचियां हैं
n :=0
अंतराल में प्रत्येक (प्रारंभ, अंत, लाभ) के लिए, करें
- यदि अंत> n, तो
  - n :=अंत
जोड़ी (प्रारंभ, अंत) डालें
A :=आकार n + 1 की सूची और 0 से भरें
अंत में 0 से A के आकार के लिए, करें
- यदि अंत d में है, तो
  - घ[अंत] में प्रत्येक (शुरुआत, लाभ) जोड़ी के लिए, करें
    - A[end] :=अधिकतम A[end], (A[start] + लाभ) और 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]]