पायथन में K कार्यों को पूरा करने के लिए अधिकतम समय खोजने का कार्यक्रम

मान लीजिए कि हमारे पास कार्यों का एक मैट्रिक्स है जहां प्रत्येक पंक्ति में 3 मान हैं। हमारे पास एक और मूल्य k भी है। हमें कार्यों से k पंक्तियों का चयन करना है, इसे S कहते हैं, जैसे कि निम्नलिखित योग कम से कम हो और योग को इस प्रकार वापस करें:अधिकतम (S[0, 0], S[1, 0], ...S[k - 1, 0]) + अधिकतम (एस [0, 1], एस [1, 1], ... एस [के - 1, 1]) + अधिकतम (एस [0, 2], एस [1, 2], ...S[k - 1, 2]) हम यह भी कह सकते हैं:3 कॉलम में से प्रत्येक एक लागत में योगदान देता है, और एस में उस कॉलम का अधिकतम मान लेकर गणना की जाती है। एक खाली का अधिकतम सूची 0 है।

इसलिए, यदि इनपुट कार्यों की तरह है =[[2, 3, 3], [4, 5, 2], [4, 2, 3]], के =2, तो आउटपुट 10 होगा, जैसे कि हम चुनते हैं पहली पंक्ति और अंतिम पंक्ति। कुल योग एस =[[2,3,3], [4,2,3]] अधिकतम (एस [0,0], एस [1,0]) =4 + अधिकतम (एस [0,1) होगा ], एस[1,1]) =3 + अधिकतम(एस[0,2], एस[1,2]) =3 =10

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

उपयोग() फ़ंक्शन को परिभाषित करें। इसमें बी लगेगा
सूची बी को क्रमबद्ध करें
yheap :=0 से K-1 की श्रेणी में प्रत्येक i के लिए -B[i, 1] वाली एक सूची
हीप को ढेर करें
Ans :=B[K - 1, 0] + (-yheap[0])
के लिए के श्रेणी में बी के आकार के लिए, करते हैं
- x :=B[i, 0]
- yheap को -B[i,1] से बदलें
- हीप का सेट आकार K के समान है
- y :=-yheap[0]
- उत्तर:=न्यूनतम उत्तर और x + y
वापसी उत्तर
मुख्य विधि से निम्न कार्य करें -
यदि A खाली है या K 0 है, तो
- वापसी 0
सूची A को क्रमित करें
B :=जोड़े की एक सूची बनाएं [A[i, 1], A[i, 2]] प्रत्येक i के लिए 0 से K-1 तक
Ans :=A[K - 1, 0] + B में प्रत्येक के लिए अधिकतम y (y, z) + B में प्रत्येक के लिए अधिकतम z (y, z)
के लिए I श्रेणी K से A के आकार में, करें
- बी में [A[i][1], A[i][2]] डालें
- Ans =न्यूनतम उत्तर और A[i, 0] + उपयोग(B)
वापसी उत्तर

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

उदाहरण

import heapq
class Solution:
   def solve(self, A, K):
      if not A or not K:
         return 0
      def util(B):
         B.sort()
         yheap = [-B[i][1] for i in range(K)]
         heapq.heapify(yheap)
         ans = B[K - 1][0] + (-yheap[0])
         for i in range(K, len(B)):
            x = B[i][0] heapq.heappushpop(yheap, -B[i][1])
            assert len(yheap) == K
            y = -yheap[0]
         ans = min(ans, x + y)
         return ans
         A.sort()
         B = [[A[i][1], A[i][2]] for i in range(K)]
         ans = A[K - 1][0] + max(y for y, z in B) + max(z for y, z in B)
         for i in range(K, len(A)):
            B.append([A[i][1], A[i][2]])
            ans = min(ans, A[i][0] + util(B))
         return ans
ob = Solution()
tasks = [ [2, 3, 3], [4, 5, 2], [4, 2, 3] ]
k = 2
print(ob.solve(tasks, k))

इनपुट

tasks = [
[2, 3, 3],
[4, 5, 2],
[4, 2, 3] ],
k = 2