Python程序：查找完成K个任务的最大时间

假设我们有一个任务矩阵，其中每一行有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。

因此，如果输入类似于 tasks = [[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 := 一个列表，对于每个i在0到K-1范围内，包含 -B[i, 1]
  • 堆化yheap
  • ans := B[K - 1, 0] + (-yheap[0])
  • 对于i从K到B的大小，执行以下操作
    • x := B[i, 0]
    • 用 -B[i,1] 替换yheap
    • 设置yheap的大小与K相同
    • y := -yheap[0]
    • ans := ans 和 x + y 的最小值
  • 返回ans
  • 从主方法执行以下操作：
  • 如果A为空或K为0，则
    • 返回0
  • 对列表A进行排序
  • B := 为每个i在0到K-1范围内创建一个包含 [A[i, 1], A[i, 2]] 的对列表
  • ans := A[K - 1, 0] + 每个 (y, z) 在 B 中的 y 的最大值 + 每个 (y, z) 在 B 中的 z 的最大值
  • 对于i从K到A的大小，执行以下操作
    • 将 [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

更新于: 2020年10月19日

314 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告