区間スケジューリングの貪欲法

終了時刻の早い順に重ならない区間を選ぶ貪欲法を実行して、選ばれる区間の集合と個数を求められる

前提

中学までに習ったことだけで始められます。

説明

いくつかの区間（会議の時間帯、機械の使用時間など）が与えられたとき、互いに重ならないように選べる区間の最大個数と、それを実現する選び方を求める技能です。手順は簡単で、区間を終了時刻の早い順に並べ、それまでに選んだ区間と重ならないものを順に取っていくだけです。教室の予約や作業の割り当てなど、『1 つの資源を時間で分け合う』場面で使います。

なぜそうしてよいのか

区間 $[s, f)$ （ただし $s < f$ ）は時刻 $s$ に始まり時刻 $f$ に終わるものとし、ある区間の終了時刻と別の区間の開始時刻が等しい場合は重ならないとみなします。終了時刻が最も早い区間を $g_{1}$ とします。重ならない区間を最も多く選んだ選び方（最適解）を 1 つ考え、その中で最も早く始まる区間を $o_{1}$ とします。 $g_{1}$ の終了時刻は全区間の中で最小なので $f (g_{1}) \leq f (o_{1})$ です。最適解の他の区間は $o_{1}$ より後に始まり、しかも $o_{1}$ と重ならないので、開始時刻はどれも $f (o_{1})$ 以上、したがって $f (g_{1})$ 以上です。よって $o_{1}$ を $g_{1}$ に取り替えても重なりは生じず、個数も変わりません。つまり『 $g_{1}$ を含む最適解』が必ず存在します。

$g_{1}$ を選んだら、残りは『開始時刻が $f (g_{1})$ 以上の区間だけを使う、より小さい同じ形の問題』になります。上の最適解から $g_{1}$ を除いたものはこの小さい問題の選び方になっているので、小さい問題で最大個数を選べば全体でも最大になります。そこでも同じ理由で、終了時刻が最も早い区間を選んでよいことがわかります。これを繰り返すのが貪欲法です。直観的には、早く終わる区間を選ぶほど後に残る時間が長くなり、後で選べる区間の可能性を最も多く残せる、ということです。

手順

すべての区間を終了時刻 $f$ の小さい順に並べる（終了時刻が等しいものの順は任意でよい）。
「最後に選んだ区間の終了時刻」を表す変数 $t$ を用意し、まだ何も選んでいないので $t = - \infty$ とする。
並べた順に区間 $[s, f)$ を 1 つずつ見て、 $s \geq t$ なら（最後に選んだ区間と重ならないので）その区間を選び、 $t \leftarrow f$ と更新する。 $s < t$ なら選ばずに飛ばす（ $t$ は変えない）。
最後まで見終わったら、選んだ区間の集合が答えの選び方であり、その個数が重ならずに選べる最大個数である。

例題

次の 8 個の区間がある。ただし区間 $[s, f)$ は時刻 $s$ に始まり時刻 $f$ に終わるものとし、一方の終了時刻と他方の開始時刻が等しいときは重ならないとみなす。
$A = [1, 3), B = [2, 5), C = [4, 7), D = [1, 8), E = [6, 9), F = [8, 10), G = [9, 12), H = [11, 13)$
終了時刻の早い順に選ぶ貪欲法を用いて、互いに重ならないように選べる区間の最大個数を求めよ。

例題の解答

手順1: 終了時刻の小さい順に並べると $A (3), B (5), C (7), D (8), E (9), F (10), G (12), H (13)$ となる（括弧内は終了時刻）。
手順2: $t = - \infty$ とする。
手順3: $A = [1, 3)$ : $1 \geq - \infty$ なので選ぶ。 $t = 3$ 。
$B = [2, 5)$ : $2 < 3$ なので飛ばす。
$C = [4, 7)$ : $4 \geq 3$ なので選ぶ。 $t = 7$ 。
$D = [1, 8)$ : $1 < 7$ なので飛ばす。
$E = [6, 9)$ : $6 < 7$ なので飛ばす。
$F = [8, 10)$ : $8 \geq 7$ なので選ぶ。 $t = 10$ 。
$G = [9, 12)$ : $9 < 10$ なので飛ばす。
$H = [11, 13)$ : $11 \geq 10$ なので選ぶ。 $t = 13$ 。
手順4: 選ばれた区間は ${A, C, F, H}$ で、個数は $4$ 。貪欲法の結果は最適なので、最大個数は $4$ である。

答え: $4$

よくある誤り

開始時刻の早い順に選んでしまう誤り。例えば $[0, 10), [1, 2), [3, 4)$ では開始が最も早い $[0, 10)$ を選ぶと 1 個しか取れないが、正しくは終了時刻順に $[1, 2), [3, 4)$ を選んで 2 個取れる。
長さの短い順に選んでしまう誤り。例えば $[0, 5), [4, 6), [5, 10)$ では最も短い $[4, 6)$ を選ぶと他の 2 つと重なって 1 個しか取れないが、正しくは終了時刻順に $[0, 5), [5, 10)$ を選んで 2 個取れる。
重なりの判定を『直前に見た区間』と比べてしまう誤り。飛ばした区間は無関係で、正しくは『最後に選んだ区間の終了時刻 $t$ 』と比べて $s \geq t$ かどうかを調べる。上の例題で $F = [8, 10)$ を直前に見た（飛ばした） $E = [6, 9)$ と比べると $8 < 9$ で重なると誤判定して飛ばしてしまうが、正しくは最後に選んだ $C = [4, 7)$ の $t = 7$ と比べて $8 \geq 7$ なので選ぶ。同様に $H = [11, 13)$ も飛ばした $G = [9, 12)$ ではなく $t = 10$ と比べて選ぶ。
端点が等しい場合の扱いを問題の約束と食い違わせる誤り。『終了時刻と開始時刻が等しいときは重ならない』なら判定は $s \geq t$ だが、閉区間 $[s, f]$ のように端点の共有も重なりとみなす約束なら判定は $s > t$ にしなければならない（例: $[1, 3]$ と $[3, 5]$ は後者の約束では同時に選べない）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

観測希望 $k$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
開始時刻 $s_{k}$	$0$	$7$	$1$	$6$	$4$	$3$	$9$
終了時刻 $f_{k}$	$6$	$11$	$4$	$8$	$7$	$5$	$10$

体験教室 $k$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
開始時刻 $s_{k}$	$2$	$1$	$4$	$6$	$3$	$8$	$7$	$10$
終了時刻 $f_{k}$	$5$	$3$	$7$	$9$	$8$	$11$	$10$	$12$

番組 $k$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$s_{k}$	$2$	$0$	$4$	$1$	$6$	$8$	$7$	$10$
$f_{k}$	$5$	$3$	$7$	$8$	$9$	$10$	$11$	$12$

予約の番号	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
開始 $s$	$1$	$2$	$4$	$1$	$5$	$8$	$9$	$11$	$10$
終了 $f$	$3$	$5$	$7$	$8$	$9$	$10$	$12$	$13$	$14$

予約	A	B	C	D	E	F	G	H	I	J
$s_{X}$	$2$	$1$	$4$	$6$	$3$	$7$	$9$	$8$	$11$	$13$
$f_{X}$	$5$	$3$	$7$	$8$	$9$	$10$	$12$	$13$	$14$	$15$

区間スケジューリングの貪欲法

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題

予約 $k$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
開始 $s_{k}$	$2$	$1$	$4$	$6$	$3$	$8$	$9$	$11$	$10$
終了 $f_{k}$	$5$	$3$	$7$	$9$	$8$	$10$	$13$	$12$	$14$