終点枕崎

プログラミングとvimと音楽と地理

区間スケジューリング問題

蟻本p43。社畜の問題です。

問題

{N} 個の仕事 {w_i\ (i=1, 2, \cdots, N)} がある。各仕事 {w_i} の開始時刻は {s_i} 、終了時刻は {t_i} である。あなたは各仕事について参加するか参加しないかを選ばなければならない。ある仕事に参加するならば、その仕事に始めから終わりまで参加しなくてはならない。すなわち、他に参加する仕事と時間か重なってはならない。開始・終了の瞬間だけが重なるのも許されない。

参加できる仕事の数の最大値を求めよ。

制約

  • {1 \leq N \leq 10^5 }
  • {1 \leq s_i < t_i \leq 10^9 }

例えば次のような仕事の集合が入力として与えられた時、
f:id:uchifuji:20171024025451p:plain
最適なスケジュール(のうちの一つ)は赤の仕事。つまり解は4。
f:id:uchifuji:20171024025445p:plain

頭の悪い人

f:id:uchifuji:20171024030424j:plain
計算量のオーダーが { O(2^n) }なのでだめ。

頭のいい人

f:id:uchifuji:20171024030920j:plain
終了時刻の早い順に貪欲に仕事を選んでいくけば最適解が求まります。計算量は平均で {O(n \log n)}。というかソートアルゴリズムに依ります。

開始時刻の早い順に貪欲に選ぶのは不正解です。
次のような仕事の場合、間違った解を導きだします。
f:id:uchifuji:20171024031738p:plain

そうパッと思いつく解法ではないですね。蟻本に証明の概略が載っていましたがいまいちピンとこないので自分で考えます。

証明

アルゴリズム {A} : 選べる仕事(今まで選んだ仕事と重なっていない仕事)の中で終了時刻が最も早いものを選ぶ。これを繰り返す。

与えられた {N} 個の仕事の集合 {W = \{ w_1, w_2, \cdots, w_N \} } に対してアルゴリズム {A} が導きだしたスケジュールに含まれる仕事の個数を {M} 、スケジュールに含まれる仕事の集合を {W' = \{ w_{k_1}, w_{k_2}, \cdots, w_{k_M} \} } とする。ただし { t_{k_1} < t_{k_2} < \cdots < t_{k_M} }{ a = \min\{ s_1, s_2, \cdots, s_N \}, b = \max\{ t_1, t_2, \cdots, t_N \} } とする。

ある仕事 {w_i \in W} があって、適当な仕事 {w_{k_j} \in W' }{W'} から選べば { t_{k_j - 1} < s_i < t_i < t_{k_j} } となる...(1) 、又は { a \leq s_i
 < t_i < t_{k_1} \lor t_{k_M} < s_i < t_i \leq b } ...(2) となると仮定する。

(1)の場合
アルゴリズム {A}{ w_{k_{j-1}} } が選ばれた時点で、開始時刻が { t_{k_{j-1}} } よりも遅い仕事を選ぶことができることは保証される。よって {w_i} は選ぶことができる仕事である。{ t_i < t_{k_j} } であるから、この時アルゴリズム {A} は仕事 {w_{k_j}} ではなく仕事 {w_{i}} を選んでいるはずである。

(2)の場合
(1)と同様の理由で、{w_i}アルゴリズム {A} によって選ばれているはずだが実際には選ばれていない。

いずれにせよ矛盾が発生するから、仮定が間違っていることがわかる。

これを言い換えると、任意の仕事 {w_i \in W} に対し、{ s_i \leq t_{k_j} \leq t_i } となるような仕事 {w_{k_j} \in W'} が存在する。

任意の合法な(時間のかぶる仕事が存在しない)仕事スケジュールを考える。その仕事スケジュールに含まれる仕事の個数を {M''} とし、このスケジュールに含まれる仕事の集合を { W'' = \{ w_{l_1}, w_{l_2}, \cdots, w_{l_{M''}} \} } とする。{ i = 1, 2, \cdots, M'' } に対し { s_{l_i} \leq t_{k_j} \leq t_{l_i} } を満たす {j} のうちの一つを {u_i} とおく。({1 \leq u_i \leq M}) このスケジュールは合法であるから、{u_1, u_2, \cdots, u_{M''}} は互いに異なる。鳩の巣原理から、{M'' \leq M} である。

より、任意の合法なスケジュールの仕事の個数は {M} を超えない。よってアルゴリズム {A} は正しい。

簡単なことを言っているのに

改めて読むと物凄く分かりにくい気がします。説明が下手なのか、はたまたアルゴリズムを数学の言葉で説明すること自体が難しいのか。図を使って説明した方がよかったと今更ながら思います。