在 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 次瀏覽

開啟您的 職業生涯

完成課程獲得認證

開始學習
廣告