Pythonで同じタイプのタスク間にk時間のギャップがあるタスクを完了するために必要な最小時間を見つけるプログラム

各項目が異なるタスクタイプを表すタスクと呼ばれる整数のリストがあるとすると、kなどの非負の整数もあります。各タスクの完了には1単位の時間がかかり、タスクは正しい順序で完了する必要がありますが、2つの同じタイプのタスクを実行する間にk単位の時間が必要です。いつでも、タスクを実行するか、待機することができます。すべてのタスクを完了するのにかかる時間を見つける必要があります。

したがって、入力がtasks =[0、1、1、2] k =2の場合、最初の2つのタスクはタイプが異なるため、出力は6になります。これにより、ギャップなしで実行できるようになります。 2、次のタスクは同じタイプのタスクであり、2つのタイムスロットを待機してからタスクを実行し、最後に他のタイプのタスクであるタイプ2を実行する必要があります。したがって、このタスクを実行します。つまり、[0、1、待機、待機、1、2]のようなものです。これから、6つのタイムスロットが必要であることがわかります。

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

• 目盛り：=0
• slot：=新しいマップ
• タスクの各tについて、
  • tf：=slot [t]（tがスロットにある場合）
  • tfがnullでなく、tf-tick> 0の場合、
    • 目盛り：=目盛り+tf-目盛り
  • 目盛り：=目盛り+1
  • slot [t]：=ティック+ k
• ダニを返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(tasks, k):
   tick = 0
   slot = {}
   for t in tasks:
      tf = slot.get(t)
      if tf is not None and tf - tick > 0:
         tick += tf - tick
      tick += 1
      slot[t] = tick + k

   return tick

tasks = [0, 1, 1, 2]
k = 2
print(solve(tasks, k))

入力

[0, 1, 1, 2]

出力

6