程序查找在Python中完成K个任务的最长时间

  • Z时代
  • 2024-01-10
  • 分类：综合

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

以上是 程序查找在Python中完成K个任务的最长时间 的全部内容， 来源链接： utcz.com/z/321726.html

回到顶部