在 Python 中找到完成所有作业的最小时间（给定约束条件）

假设我们有一个作业数组，其中包含不同的时间需求，有 k 个不同的分配者来分配作业，我们还知道分配者完成一个单位作业需要多少时间 t。我们必须在以下约束条件下找到完成所有作业的最小时间。

  • 一个分配者只能分配连续的作业。

  • 两个分配者不能共享或执行单个作业。

因此，如果输入类似于 k = 4，t = 5，job = {12, 6, 9, 15, 5, 9}，则输出将为 75，因为我们通过分配 [12]、[6, 9]、[15] 和 [5, 9] 得到这个时间。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数 is_valid()。这将采用时间、K 和作业作为参数。

  • n := 作业的大小

  • count := 1，curr_time := 0，i := 0

  • 当 i < n 时，执行：

    • 如果 curr_time + job[i] > time，则

      • curr_time := 0

      • count := count + 1

    • 否则，

      • curr_time := curr_time + job[i]

      • i := i + 1

  • 当 count <= K 时返回 true

  • 从主方法中，执行以下操作：

  • n := 作业的大小

  • end := 0，begin := 0

  • 对于 i 的范围从 0 到 n，执行：

    • end := end + job[i]

  • res := end

  • job_max := job 的最大值

  • 当 begin <= end 时，执行：

    • mid := ((begin + end) / 2) 取整

    • 如果 mid >= job_max 且 is_valid(mid, K, job) 为 true，则

      • res := res 和 mid 的最小值

      • end := mid - 1

    • 否则，

      • begin := mid + 1

  • 返回 res * T

示例

让我们看看以下实现以更好地理解：

实时演示

def is_valid(time, K, job):
   n = len(job)
   count = 1
   curr_time = 0
   i = 0
   while i < n:
      if curr_time + job[i] > time:
         curr_time = 0
         count += 1
      else:
         curr_time += job[i]
         i += 1
   return count <= K
def get_minimum_time(K, T, job):
   n = len(job)
   end = 0
   begin = 0
   for i in range(n):
      end += job[i]
   res = end
   job_max = max(job)
   while begin <= end:
      mid = int((begin + end) / 2)
      if mid >= job_max and is_valid(mid, K, job):
         res = min(res, mid)
         end = mid - 1
      else:
         begin = mid + 1
   return res * T
job = [12, 6, 9, 15, 5, 9]
k = 4
T = 5
print(get_minimum_time(k, T, job))

输入

4, 5, [12, 6, 9, 15, 5, 9]

输出

75

更新于：2020-08-25

433 次浏览

开启您的 职业生涯

完成课程获得认证

开始学习
广告