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

สมมติว่าเรามีเมทริกซ์ของงานที่แต่ละแถวมีค่า 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

ดังนั้นหากอินพุตเป็นเหมือนงาน =[[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 + สูงสุด (S[0,2], S[1,2]) =3 =10

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน util() นี่จะใช้เวลา B
• เรียงลำดับรายการ B
• yheap :=รายการที่มี -B[i, 1] สำหรับแต่ละ i ในช่วง 0 ถึง K-1
• heapify yheap
• เช่น :=B[K - 1, 0] + (-yheap[0])
• สำหรับฉันในช่วง K ถึงขนาด B ทำ
  • x :=B[i, 0]
  • แทนที่ yheap ด้วย -B[i,1]
  • ขนาดชุดของ yheap เท่ากับ K
  • y :=-yheap[0]
  • ans :=ขั้นต่ำของ ans และ x + y
• คืนสินค้า
• จากวิธีหลัก ให้ทำดังนี้ -
• ถ้า A ว่างเปล่าหรือ K เป็น 0 แล้ว
  • คืน 0
• เรียงลำดับรายการ A
• B :=ทำรายการคู่ [A[i, 1], A[i, 2]] สำหรับแต่ละ i ในช่วง 0 ถึง K-1
• ans :=A[K - 1, 0] + สูงสุด y สำหรับแต่ละ (y, z) ใน B + สูงสุด z สำหรับแต่ละอัน (y, z) ใน B
• สำหรับฉันในช่วง K ถึงขนาด A ทำ
  • แทรก [A[i][1], A[i][2]] ลงใน B
  • ans =ขั้นต่ำของ ans และ 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

ผลลัพธ์

10