Pythonで指定された制約を使用してすべてのジョブを完了するための最小時間を見つける

さまざまな時間要件を持つ一連のジョブがあり、ジョブを割り当てる人がk人いて、担当者が1つのジョブユニットを実行するのにかかる時間もあるとします。次の制約ですべてのジョブを完了するための最小時間を見つける必要があります。

• 担当者には、連続するジョブのみを割り当てることができます。

• 2人の担当者が1つのジョブを共有または実行することはできません。

したがって、入力がk =4、t =5、job ={12、6、9、15、5、9}の場合、今回は[12]、[6]を割り当てると、出力は75になります。 、9]、[15]および[5、9]

これを解決するには、次の手順に従います-

• 関数is_valid（）を定義します。これには時間がかかります、K、仕事

• n：=ジョブのサイズ

• count：=1、curr_time：=0、i：=0

• i

  • curr_time + job [i]> timeの場合、

    • curr_time：=0

    • count：=count + 1

  • それ以外の場合

    • curr_time：=curr_time + job [i]

    • i：=i + 1

• count <=K

  の場合はtrueを返します

• mainメソッドから、次のようにします<

• n：=ジョブのサイズ

• 終了：=0、開始：=0

• 0からnの範囲のiの場合、実行

  • end：=end + job [i]

• res：=end

• job_max：=ジョブの最大値

• 開始<=終了、実行

  • mid：=（（begin + end）/ 2）整数部分を取る

  • mid> =job_maxおよびis_valid（mid、K、job）がtrueの場合、

    • res：=最小解像度、中間

    • 終了：=半ば-1

  • それ以外の場合

    • 開始：=mid + 1

• 戻り値*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