この問題は、加重間隔スケジューリングの問題に似ていると思いますが、少し異なります。
シフトがあるとしましょう s 開始時間と終了時間があり、シフトには n 埋めるスロット s.start に s.end。スロットは、s.startからs.endまでの充填可能な時間範囲です。あなたは与えられます m 間隔。各間隔には開始時刻と終了時刻があります。スロットに間隔を割り当て、 必要最小限のスロット数を使用するように。重複する間隔がない限り、間隔をスロットに割り当てることができます。与えられた間隔 知られている 指定された数のスロットに収まるようにします（ただし、スロットを埋める必要はありません）。 私 スロットに割り当てられている場合、そのスロットは 私の時間範囲。
私はブルートフォースを行うjsbinを作成しましたこのためのアルゴリズムですが、間隔の可能なすべてのシーケンスをチェックし、競合のない最初のスロットに貪欲に配置しようとするため、O（n！）以下です。
http://jsbin.com/bixalabume/1/edit?js,console （私は間隔を「セグメント」と呼びます。）
この問題は妥当な時間で解決できますか？ DPソリューションがあるように感じますが、1つは考えられません。
私はこの種のプログラミングに特に強いわけではありませんが、私が見たが理解できなかったいくつかの同様の質問がありました。
- https://cs.stackexchange.com/questions/42008/weighted-interval-scheduling-with-m-machines -同様ですが、私の問題には重み付き間隔がありません（私は思います）
- アポイントメントスケジューリングアルゴリズム（N人の空きビジースロット、制約の満足度） （これはスロットのタイミングが可変であるため、より複雑ですが、私のスロットは同じタイミングです）
回答：
回答№1は2これはグラフ彩色で解決できます。間隔ごとに頂点を作成し、対応する間隔が重なる場合は、頂点に他の頂点とのリンクがあります。これにより、干渉グラフが自動的に間隔グラフになります。これは、グラフを作成しなくても、非常に簡単に色付けできます。間隔を開始時間で並べ替え、最初のスロットに1つずつ挿入します。新しい色が必要になるため、これが最適になります k 挿入するときは、 k - 1 挿入される間隔の開始時に色が占有されていたため、少なくとも k その時点で間隔が重なっているため、より少ない間隔を指定することはできませんでした。 k とにかく色。