タイムテーブルイベントパッキング

Question

私は学校の目的のためのタイムテーブルに取り組んでいます。私はイベントの時間順リストを受け取り、私の目標はそれらをタイムライン上に描画することです。問題は、あるイベントが別のイベントと重なっていることです（下の図に示すように）。私がしたいことは、可能な限り小さなスペースにこのイベントを「パック」することです。 This is single day with overlapping events.

最初の画像は、私がこれまでにやったことを示しています。画像上に見られるように、長方形は互いに交差しておらず、空きスペースをきちんと埋めています。しかし、私は順序の合理的なアルゴリズムを考え出すことはできませんでした。 Second picture shows how events should be ordered.

これは古典的なパッキングの問題から、この問題は異なるする二つの条件である：

1. イベント（開始および終了によって定義される）は、x座標を与えています。
2. イベントの幅は固定されていますが、高さは任意です。

Answer 1

この問題は、ファイルシステムの断片化の問題を少し思い起こさせます。簡単な解決策は、有名なアルゴリズムの1つ、例えば、ファーストフィットまたはベストフィット。

しかし、私はあなたに最適な解決策が欲しいと思います。だから私はbacktracking algorithmを実装することを提案しています。私は長いランタイムを引き起こす可能性があることに注意してくださいが、私はこれがあなたの文脈で本当に重要ではないと思う。