পাইথনে 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, ২], ...এস তালিকা হল 0.

সুতরাং, যদি ইনপুট টাস্কস =[[2, 3, 3], [4, 5, 2], [4, 2, 3] ], k =2 এর মত হয়, তাহলে আউটপুট 10 হবে, যেন আমরা বাছাই করি। প্রথম সারি এবং শেষ সারি। মোট যোগফল হবে S =[[2,3,3],[4,2,3]] সর্বোচ্চ(S[0,0], S[1,0]) =4 + সর্বোচ্চ(S[0,1] ], S[1,1]) =3 + সর্বোচ্চ(S[0,2], S[1,2]) =3 =10

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন util() সংজ্ঞায়িত করুন। এটি B
তালিকা বাছাই করুন B
yheap :=0 থেকে K-1 রেঞ্জের প্রতিটি i-এর জন্য -B[i, 1] সহ একটি তালিকা
heapify yheap
উত্তর :=B[K - 1, 0] + (-yheap[0])
আমি K থেকে B আকারের রেঞ্জের জন্য, কর
- x :=B[i, 0]
- -B[i,1] দ্বারা yheap প্রতিস্থাপন করুন
- yheap-এর সেট আকার K-এর মতই
- y :=-yheap[0]
- উত্তর :=সর্বনিম্ন উত্তর এবং x + y
উত্তর ফেরত দিন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
যদি A খালি হয় বা K 0 হয়, তাহলে
- রিটার্ন 0
তালিকা A সাজান
B :=0 থেকে K-1 রেঞ্জের প্রতিটি i এর জন্য [A[i, 1], A[i, 2]] জোড়ার একটি তালিকা তৈরি করুন
উত্তর :=A[K - 1, 0] + B-এ প্রতিটি (y, z) এর জন্য সর্বাধিক y + B তে প্রতিটি(y, z) এর জন্য সর্বাধিক z
আমি K থেকে A আকারের রেঞ্জের জন্য, কর
- বি-তে [A[i][1], A[i][2]] ঢোকান
- উত্তর =সর্বনিম্ন উত্তর এবং A[i, 0] + util(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