問題
$1$ 台の処理機（マシン）と $N$ 個のジョブがある。ジョブ $i$ は「解禁時刻 $r_i$」「締切 $d_i$」「処理時間 $p_i$」を持ち、時刻 $r_i$ 以降でなければ実行を開始できず、時刻 $d_i$ までに処理を完了しなければならない。マシンは同時に1つのジョブしか処理できないが、任意の時刻でジョブの実行を中断し、後で再開する（プリエンプション）ことが自由に許される。
すべてのジョブを、それぞれの締切までに完了させることが可能かどうかを判定せよ。
これは古典的なリアルタイムスケジューリング理論の問題であり、「単一マシン・プリエンプション許可」の設定では EDF法（Earliest Deadline First：常にその時点で締切が最も早い、未完了かつ解禁済みのジョブを実行する）が最適スケジュールを与えることが知られている（Horn の定理, 1974）。したがって、EDF法に従ってスケジュールをシミュレートし、締切に間に合わないジョブが1つでも生じればそのスケジューリング問題自体が実行不可能である。
入力形式
N
r_1 d_1 p_1
r_2 d_2 p_2
:
r_N d_N p_N制約
入出力例
入力例1
3
0 2 1
0 2 1
0 3 1出力例1
Yes入力例2
2
0 1 1
0 1 1出力例2
No概念図
ヒント（段階的開示）
ヒント1（方向性）
「早い者勝ち」でも「短いジョブ優先」でもなく、「締切が早いジョブを優先する」という直感的なルールが、なぜプリエンプション許可下では最適（実行可能なスケジュールが存在するなら、EDFで組んだスケジュールも必ず実行可能になる）と言えるのか、まずその直感を掴むことが重要である。感覚的には「締切が早いジョブを後回しにすると、そのジョブは二度と『間に合う』チャンスを取り戻せないが、締切が遅いジョブは後回しにしても被害が少ない」という非対称性がある。
ヒント2（アプローチ）
時間を「解禁イベント」の起きる時刻ごとに区切って考える。各区間では、その時点で「解禁済みかつ未完了」なジョブの中から締切が最小のものを選んで実行し続け、次のイベント（新しいジョブの解禁、またはそのジョブの完了）が起きるまで継続する。これは優先度付きキュー（締切をキーとする最小ヒープ）を使えば効率的にシミュレートできる。ジョブが完了した瞬間に、その完了時刻がジョブ自身の締切を超えていれば、その時点で「実行不可能」と判定してよい。
ヒント3（誘導）
import heapq
def is_feasible(jobs): # jobs: list of (r, d, p)
n = len(jobs)
order = sorted(range(n), key=lambda i: jobs[i][0])
heap = [] # (deadline, remaining, job_index)
t = 0
idx = 0
while idx < n or heap:
while idx < n and jobs[order[idx]][0] <= t:
r, d, p = jobs[order[idx]]
heapq.heappush(heap, (d, p, order[idx]))
idx += 1
if not heap:
t = jobs[order[idx]][0]
continue
d, p, i = heapq.heappop(heap)
next_release = jobs[order[idx]][0] if idx < n else float('inf')
run = min(p, next_release - t)
t += run
p -= run
if p > 0:
heapq.heappush(heap, (d, p, i))
else:
if t > d:
return False
return True「今処理中のジョブを、次の解禁イベントが来るまで走らせ続け、走らせきれなければ残り時間をヒープに戻す」という区間分割の考え方がポイント。
模範解答 (Python)
import sys
import heapq
def main():
data = sys.stdin.buffer.read().split()
idx = 0
n = int(data[idx]); idx += 1
jobs = []
for _ in range(n):
r = int(data[idx]); idx += 1
d = int(data[idx]); idx += 1
p = int(data[idx]); idx += 1
jobs.append((r, d, p))
order = sorted(range(n), key=lambda i: jobs[i][0])
heap = []
t = 0
j = 0
feasible = True
while j < n or heap:
while j < n and jobs[order[j]][0] <= t:
r, d, p = jobs[order[j]]
heapq.heappush(heap, (d, p, order[j]))
j += 1
if not heap:
t = jobs[order[j]][0]
continue
d, p, i = heapq.heappop(heap)
next_release = jobs[order[j]][0] if j < n else float('inf')
run = min(p, next_release - t)
t += run
p -= run
if p > 0:
heapq.heappush(heap, (d, p, i))
else:
if t > d:
feasible = False
break
print("Yes" if feasible else "No")
main()Step-by-Step 解説
任意の実行可能なスケジュール $\sigma$ が存在するとする。もし $\sigma$ の中で「締切が早いジョブA」より前に「締切が遅いジョブB」が実行されている箇所があれば、その部分の実行順序を交換しても両方とも締切に間に合うことを示せる。この交換を繰り返すことで、任意の実行可能スケジュールを「常に締切最小のジョブを実行する」EDFスケジュールへと、実行可能性を保ったまま変形できる。
意思決定が変化しうるのは「新しいジョブが解禁される瞬間」と「実行中のジョブが完了する瞬間」のみである。したがって、時刻を1ずつ進める必要はなく、「次の解禁時刻」と「現在実行中のジョブが完了する時刻」の早い方まで一気に時間を進めれば十分。
「解禁済みかつ未完了」のジョブの集合の中から締切最小のものを $O(\log N)$ で取り出すために、(締切, 残り処理時間, ジョブ番号) をキーとする最小ヒープを使う。走らせきれなかった場合は残り処理時間を更新して再びヒープに戻す。この「戻す」操作がプリエンプションのシミュレーションに対応する。
あるジョブの残り処理時間が0になった（完了した）瞬間に、その時点の時刻 $t$ が締切 $d$ を超えていれば、その場で "No" と判定してよい。EDFが最適であることから、「EDFで組んで間に合わないなら他のどんな組み方でも間に合わない」ため、途中で打ち切って判定を確定できる。
各ジョブは高々 $O(1)$ 回ヒープに出入りし、全体のイベント数は $O(N)$ に抑えられる。したがって全体で $O(N\log N)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 締切が早い方でなく「処理時間が短い方（SJF）」を優先してしまう | 通常のスケジューリング直感（SJFは平均完了時間最小化に有効）と混同する | 締切に関する実行可能性判定ではEDF（締切最小優先）が最適である点を区別する |
| 時刻を1ずつ進めるシミュレーションにしてしまう | 素朴な実装のまま高速化を怠る | 「次の解禁時刻」と「現在のジョブの残り処理時間」の最小値だけ時間を進めるイベント駆動方式にする |
| ジョブが部分的に実行された後、残り時間をヒープに戻し忘れる | プリエンプションの概念を「そのジョブは終わり」と誤解する | if p > 0: heapq.heappush(...) を必ず入れ、中断されたジョブを正しく再キューする |
| ヒープが空なのに次の要素にアクセスしてエラーになる | 解禁待ちの空白期間（マシンがアイドル）を考慮していない | ヒープが空なら次の解禁時刻まで t を直接進める分岐を入れる |
| 締切ちょうど（t=d）を不可能と誤判定する | 不等号の向きを逆にする（t>=d にしてしまう） | 「時刻dちょうどに完了」は間に合っているとみなし、t > d のときのみ不可能とする |
次のステップ
- 発展: 実行可能と判定された場合に、実際のプリエンプティブスケジュール（各ジョブがどの時間区間でどれだけ実行されたか）を復元して出力するプログラムに拡張せよ。
- 発展2: マシンが $M\ge2$ 台に増えた場合（プリエンプション許可・均一並列マシン）の実行可能性判定は、EDFの単純な一般化では最適にならないことが知られている（Dertouzos & Mok, 1989 の反例など）。$M$ 台版で正しい判定条件を定式化せよ。