Chương trình tìm thời gian tối đa hoàn thành K tác vụ bằng Python

Cho ma trận tasks mỗi hàng 3 giá trị và số k. Chọn k hàng sao cho tổng: max(cột 0) + max(cột 1) + max(cột 2) là nhỏ nhất. Trả về tổng này.

Ví dụ: tasks = [[2,3,3], [4,5,2], [4,2,3]], k = 2 → 10 (chọn hàng 0 và 2: max cột 0=4, cột 1=3, cột 2=3, tổng=10).

Quy trình giải quyết

1. Sắp xếp tasks theo cột 0.
2. Dùng heap để duy trì top k giá trị cột 1 và cột 2.
3. Duyệt các hàng, cập nhật heap và tính tổng tối thiểu.
4. Phức tạp O(n log n).

Ví dụ mã nguồn

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

Đầu vào

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

Đầu ra

10