仕事の割り当て

ファクトリーの問題について考えていたと思ったら、謎の問題を考えていた。

仕事がn個あり、各仕事は時刻s_kに始まり、時刻e_kに終わる。(e_kを含む)
各仕事をm個のラインに割り当てる。
ここで1つの仕事は1つのラインで完全にやりとげなければならず、また1つのラインは同時に1つまでしか仕事はできない。
m個より多くの仕事の区間で覆われている時刻が存在しないならば、すべての仕事を割り当てることができることを証明せよ。

与えられた仕事の並び順は関係ないので、仕事は開始時刻の順に並んでいるものとしてよい。
k個目までの仕事はすべて割り当てられることができることをkについての帰納法で証明する。

まず、0個目までの仕事は明らかに全て割り当てることができる。
k-1個目までの仕事をすべて割り当てることができたとする。
このとき、m個より多くの仕事の区間で覆われている時刻が存在しないことから、時刻s_kにまだ割り当てがないラインlがある。
またk-1個目までの仕事はすべて開始時刻がs_k以下であったから、ラインlは時刻s_k以降にもまだ割り当てはひとつもない。
よってk-1個目までの仕事の割り当てはそのままに、ラインlにk個目の仕事を割り当てることができる。
したがってk個目までの仕事をすべて割り当てることができる。

□

要は開始時刻が早い仕事から順に、その時刻に空いているラインに割り当てればいいってだけ。
なんだか当たり前のことのような気もするが、証明するまで成り立つのかどうか自信がなかった