假设我们有一个任务矩阵，其中每行有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。
因此，如果输入类似于task = [[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 + max（S [0,2]，S [1,2]）= 3 = 10
为了解决这个问题，我们将遵循以下步骤-
定义一个功能util()。这需要B
排序列表B
yheap：=对于范围为0至K-1的每个i，带有-B [i，1]的列表
堆码
ans：= B [K-1，0] +（-yheap [0]）
对于范围在K到B的i，
x：= B [i，0]
用-B [i，1]替换yheap
设置的大小与K相同
y：= -yheap [0]
ans：= ans和x + y的最小值
返回ans
从主要方法中执行以下操作-
如果A为空或K为0，则
返回0
排序列表A
B：=为范围为0至K-1的每个i组成对[A [i，1]，A [i，2]]的列表
ans：= A [K-1，0] + B中每个(y,z)的y的最大值+ B中每个(y,z)的z的最大值
对于范围在K到A的i
将[A [i] [1]，A [i] [2]]插入B
ans = 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
输出结果
10