পাইথনে K টাস্ক ফিনিশ করার সর্বোচ্চ সময় খুঁজে বের করার প্রোগ্রাম

মান ল করুন tasks নামের একটি ম্যাট্রিক্স যেখানে প্রতিটি সারিতে ৩টি মান আছে। আরেকটি মান k আছে। আমাদের tasks থেকে kটি সারি বেছে নিতে হবে, একলো S বললে, নিচের যোগফল ন্যূনতম করতে হবে এবং সেই যোগফল ফেরত দিতে হবে: max(S[0,0], S[1,0], ...S[k-1,0]) + max(S[0,1], S[1,1], ...S[k-1,1]) + max(S[0,2], S[1,2], ...S[k-1,2])। অর্থাৎ ৩টি কলামই খরচে অবদান রাখে, এবং সেটি S-এ ওই কলামের ম্যাক্স ভ্যালু लेकर হিসাব করা হয়। খালি লিস্টের ম্যাক্স ০।

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

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

একটি util() ফাংশন সংজ্ঞায়িত করুন। এটি B গ্রহণ করবে।
B তালিকাটি সাজান।
yheap := [-B[i][1] for i in range(K)] তালিকা বানান এবং heapify করুন।
ans := B[K-1][0] + (-yheap[0])
i কে K থেকে B-এর আকার পর্যন্ত লুপ চালান:
- x := B[i][0]
- yheap-এ -B[i][1] রিপ্লেস করুন
- yheap-এর আকার K রাখুন
- y := -yheap[0]
- ans := min(ans, x + y)
ans ফেরত দিন
মূল মেথড থেকে: যদি A খালি বা K ০ হয়, ০ ফেরত দিন। A সাজান। 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)। i কে K থেকে A-এর আকার পর্যন্ত লুপ চালান: B-এ [A[i][1], A[i][2]] যোগ করুন, ans = min(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