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

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

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

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

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

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

उदाहरण

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

आउटपुट

10