โปรแกรมหาเวลาสูงสุดในการทำ K งานใน Python

สมมติว่าเรามีเมทริกซ์งานแต่ละแถวมี 3 ค่า และค่า k เลือก k แถว เรียกว่า S ให้ผลรวมนี้น้อยที่สุด: max(S[:,0]) + max(S[:,1]) + max(S[:,2]) แต่ละคอลัมน์มีค่าใช้จ่ายคือค่าสูงสุดในคอลัมน์นั้นของ S

ตัวอย่าง: tasks = [[2,3,3],[4,5,2],[4,2,3]], k = 2 ผลลัพธ์ 10 (เลือกแถว 1 และ 3: max(2,4)=4 + max(3,2)=3 + max(3,3)=3 = 10)

ขั้นตอนการแก้ปัญหา

1. ฟังก์ชัน util(B):
   • เรียง B
   • yheap = [-B[i][1] for i in range(K)], heapify
   • ans = B[K-1][0] + (-yheap[0])
   • วนลูป i จาก K ถึง len(B)-1:
     • x = B[i][0]
     • heapq.heappushpop(yheap, -B[i][1])
     • y = -yheap[0]
     • ans = min(ans, x + y)
   • คืนค่า ans
2. จากเมธอดหลัก:
   • ถ้า A ว่างหรือ K=0 คืนค่า 0
   • เรียง 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 ถึง len(A)-1:
     • เพิ่ม [A[i][1], A[i][2]] เข้า B
     • ans = min(ans, A[i][0] + util(B))
   • คืนค่า ans

ตัวอย่างโค้ด Python

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))  # Output: 10

อินพุต / เอาต์พุต

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

Output: 10