Task Scheduler
大文字のアルファベットで構成される文字列 tasks と、整数 n が与えられます。プロセッサは、任意の順序で1単位時間に1つのタスクを実行するか、1単位時間アイドル状態になります。
同じ文字の2回の実行の間には、少なくとも n 単位時間が必要です。単位時間 t に実行された文字は、最短で単位時間 t+n+1 に再び実行できます。すべてのタスクを実行するために必要な最小の単位時間数を返してください。
関数
- tasksstring
- 各タスクに大文字を1文字ずつ
- ninteger
- 同じ文字の2つの連続区間の間にある最小の単位数
- 戻り値integer
- アイドル状態のものも含めた、単位の最小数
制約
1 ≤ tasks.length ≤ 104tasksには、大文字の英字AからZのみが含まれます。0 ≤ n ≤ 100
例
- 入力
- tasks = "CACBAC"n = 2
- 出力
- 7
- 説明
- C は 3 回実行され、実行間に 2 単位ずつあるため、C の実行だけで 7 単位にわたります。
C A B C Aの順序では、アイドル時間を挟んで、A と B で隙間を埋め、アイドル時間が 1 単位必要です。7
- 入力
- tasks = "ABCABD"n = 1
- 出力
- 6
- 説明
- A と B はそれぞれ 2 回実行され、実行の間には 1 単位の間隔があります。順序
A B C A B Dなら、アイドル時間を挟まずに A と B を離して配置できるため、答えはタスク数の6です。
- 入力
- tasks = "ZZZ"n = 3
- 出力
- 9
- 説明
- 実行されるのは Z だけなので、すべての間隔がアイドル状態です：Z、3 つのアイドル単位、Z、3 つのアイドル単位、Z。これは
9単位です。
発展問題
最短のスケジュールも1つ、アイドル単位ごとに.を含む文字列として返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
どの文字によって待機時間が避けられなくなるでしょうか？最も頻繁に現れる文字と、その連続部分同士がどれほど離れていなければならないかを考えてみましょう。
最も出現頻度の高い文字を最初に配置します。連続した並びを1つ、空きスロットを
n個、さらに連続した並びを1つ、というように続けます。これには何単位必要で、空きスロットには何を入れられるでしょうか？topを最大の出現回数、atTopをその回数で出現する文字の数とすると、フレームは(top-1) × (n+1) + atTop単位を占めます。タスクの数と比較してください。
解説
実行順序は自分で決められるので、アイドル単位をどれだけ少なくできるかが問題です。最も頻度の高い文字によって決まります。その文字の実行は n+1 単位ずつ間隔を空けて配置し、ほかのタスクでその間を埋めます。最大ヒープを使って頻度の高い文字から実行するか、1つの式で隙間を直接数えます。
最大ヒープを使ってラウンドをシミュレートする
考え方
時間を n+1 単位のラウンドに区切ります。各ラウンドで同じ文字を2回実行することはできません。また、あるラウンドの特定のスロットで実行した文字は、ちょうど n+1 単位後の次のラウンドの同じスロットで再び実行できます。各ラウンドでは、残りのコピー数が最も多い文字を実行します。それらの残りの実行は n+1 単位の間隔を空ける必要があるため、最後にアイドル時間を発生させる可能性があるのはそれらです。先に実行することで、個数を均等に保てます。
作業が残るラウンドは n+1 単位かかり、空きスロットはアイドル時間になります。最後のラウンドは、実行したタスク分だけかかります。例1では、ラウンドごとに C A B、次に C A とアイドル時間1単位、最後に C を実行します。つまり、3 + 3 + 1 = 7 です。1回の pop で1つのタスクを実行するため、タスクが m 個、文字が k ≤ 26 種類の場合、計算量は O(m log k) です。
アルゴリズム
- 各文字を数え、0より大きい個数を最大ヒープに入れます。
- ヒープが空でない間、ラウンドを実行します。最大
n+1個の個数を取り出し、1減らしてもまだ0より大きい個数をそれぞれ残します。 - 残した個数をヒープに戻します。
- ヒープが空でなければ時間に
n+1を加え、そうでなければ、そのラウンドで実行したタスク数を加えます。 - 時間を返します。
import heapq
from collections import Counter
def leastInterval(tasks, n):
# heapq is a min-heap, so store negated counts to pop the largest first.
heap = [-c for c in Counter(tasks).values()]
heapq.heapify(heap)
time = 0
while heap:
# One round of n+1 slots: run the most frequent tasks left, each at most once.
left = []
ran = 0
while ran < n + 1 and heap:
c = -heapq.heappop(heap)
ran += 1
if c > 1:
left.append(c - 1)
for c in left:
heapq.heappush(heap, -c)
# A round lasts n+1 units, idle included; the last one ends with its last task.
time += n + 1 if heap else ran
return time最も頻出する文字のフレーム数を数える
考え方
topを、文字Xが持つ最も多い出現回数とします。最後の連続部分を除き、各連続部分の後にn個の空きスロットを設けてXを配置します。つまり、n+1単位のフレームをtop-1個並べ、その後にXの最後の連続部分を置きます。top個未満しかない文字は空きスロットに収まり、各フレームに1つずつ配置されるため、それらの出現間隔は少なくともn+1になります。top個出現する他の各文字は、末尾に1単位を加えます。最も多く出現する文字がatTop個ある場合、必要な単位数は(top-1) × (n+1) + atTopです。
これより短いスケジュールはありません。最初の(top-1) × (n+1)単位を、n+1単位のウィンドウtop-1個に分けます。各ウィンドウ内では、最も多く出現する各文字は最大1回しか実行できないため、ウィンドウの後にもそれらatTop個すべてに、まだ実行されていない分が残ります。タスクの数が空きスロットより多い場合は、一部のフレームをn+1より長くします。フレームが長くなれば間隔も広がるだけなので、アイドル時間は発生せず、答えはmになります。答えは2つの値の大きい方です。
アルゴリズム
- 26文字それぞれの個数を数えます。
- 最大の個数である
topと、その個数を持つ文字の数であるatTopを求めます。 frames = (top-1) × (n+1) + atTopを計算します。framesとタスク数のうち、大きい方を返します。
def leastInterval(tasks, n):
counts = [0] * 26
for ch in tasks:
counts[ord(ch) - ord("A")] += 1
top = max(counts)
at_top = counts.count(top) # tasks that share the highest count
# top-1 full frames of n+1 units, then one last slot per task at the top count.
frames = (top - 1) * (n + 1) + at_top
# With more tasks than frame slots, no idle unit is needed at all.
return max(frames, len(tasks))
落とし穴と境界ケース
- 最上位で同数になった文字を数え忘れる。
n = 5の"MMNNPP"では、3つの文字すべての出現回数が2なので、答えは7ではなく(2-1) × 6 + 3 = 9です。 - 大きい方を選ぶ手順を忘れる。例2では、フレームから
(2-1) × 2 + 2 = 4となりますが、タスクは6つあるため、少なくとも6単位必要です。 - 最後のラウンドにも
n+1単位を丸ごと加算する。最後のタスクの後に待ち時間はありません。例3では、9ではなく12になってしまいます。 - ラウンド中に出現回数を戻す。同じ文字がそのラウンド中に再び取り出され、間隔が短すぎる状態で2回実行される可能性があります。
よくある質問3
Task Scheduler の時間計算量はどれくらいですか？
文字を数える処理にはタスクが m 個の場合 O(m) かかり、その後、数式で26個のカウントを読み取るため、解法の時間計算量は O(m)、追加メモリは O(1) です。最大ヒープによるシミュレーションではタスクごとに1回取り出すため、文字の種類を k ≤ 26 とすると O(m log k) です。
タスク スケジューラでアイドル時間が不要なのはどのような場合ですか？
m ≥ (top-1) × (n+1) + atTop のとき、タスクは空いているスロットをすべて埋め、隙間を残すのではなくフレームを伸ばすため、答えは m です。例 2 の "ABCABD" と n = 1 は、このケースに該当します。
入力文字列の順序は重要ですか？
いいえ。タスクを実行する順序は自分で選べるので、重要なのは各文字が何回現れるかだけです。"CACBAC"と"CCCAAB"は、n = 2の場合、どちらも7単位必要です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def leastInterval(tasks, n):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
tasks = "CACBAC" n = 2
期待される出力
7