Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm thời gian tối đa để hoàn thành K nhiệm vụ trong Python

Giả sử chúng ta có một ma trận nhiệm vụ trong đó mỗi hàng có 3 giá trị. Chúng ta cũng có một giá trị khác k. Chúng ta phải chọn k hàng từ nhiệm vụ, gọi nó là S, sao cho tổng sau là cực tiểu và trả về tổng là:tối đa của (S [0, 0], S [1, 0], ... S [k - 1, 0]) + tối đa của (S [0, 1], S [1, 1], ... S [k - 1, 1]) + tối đa của (S [0, 2], S [1, 2], ... S [k - 1, 2]) Chúng ta cũng có thể nói như sau:Mỗi cột trong số 3 cột đóng góp vào một chi phí và được tính bằng cách lấy giá trị lớn nhất của cột đó trong S. Giá trị lớn nhất của một ô trống danh sách là 0.

Vì vậy, nếu đầu vào giống như các nhiệm vụ =[[2, 3, 3], [4, 5, 2], [4, 2, 3]], k =2, thì đầu ra sẽ là 10, như thể chúng ta chọn hàng đầu tiên và hàng cuối cùng. Tổng tổng sẽ là 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

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một hàm dùng (). Điều này sẽ mất B
  • sắp xếp danh sách B
  • yheap:=một danh sách có -B [i, 1] cho mỗi i trong phạm vi từ 0 đến K-1
  • heapify yheap
  • ans:=B [K - 1, 0] + (-yheap [0])
  • đối với tôi trong phạm vi K đến kích thước là B, thực hiện
    • x:=B [i, 0]
    • thay thế yheap bằng -B [i, 1]
    • kích thước đặt của yheap giống với K
    • y:=-yheap [0]
    • ans:=tối thiểu ans và x + y
  • trả lại ans
  • Từ phương thức chính, hãy làm như sau -
  • nếu A trống hoặc K bằng 0, thì
    • trả về 0
  • sắp xếp danh sách A
  • B:=tạo danh sách các cặp [A [i, 1], A [i, 2]] cho mỗi i trong phạm vi từ 0 đến K-1
  • ans:=A [K - 1, 0] + tối đa của y cho mỗi (y, z) trong B + tối đa z cho mỗi (y, z) trong B
  • đối với tôi trong phạm vi K đến kích thước là A, thực hiện
    • chèn [A [i] [1], A [i] [2]] vào B
    • ans =tối thiểu ans và A [i, 0] + use (B)
  • trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

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))

Đầu vào 

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

Đầu ra 

10