私の問題の抽象化は、デカルト平面にはたくさんの長方形があるということです。これらの長方形は既知の整数サイズを持ち、横座標 (水平座標) が既知で固定されている整数座標を持っている必要があります。縦座標 (垂直座標) のみが異なる場合があります。
問題は、指定されたすべての長方形を含む最小の長方形が最小である縦座標を見つけることです。これは、小さな長方形の横座標が固定されているため、幅が固定されているため、最小の高さを持つ必要があることを意味します。
バックトラッキングを使用する必要があるかどうか、またはより高速な方法があるかどうかはわかりません.50個の長方形では、正しい解を計算するのにかなりの時間がかかり、貪欲なアルゴリズムはうまくいきません。
編集：申し訳ありませんが、私は十分に明確ではなかったことに気づきました。最初にこの質問をしたとき、私はカレンダー アプリケーションを作成していました。マネージャーは、チームのイベントを次のように入力します。
- イベントAは午後2時から。午後4時に終了します。
- イベントBは17時から。午後6時に終了します。
- イベントCは16時から。午後6時に終了します。
- イベントDは午後2時から。午後3時に終了します。
- イベントEは午後3時から。午後5時に終了します。
これらのイベントをタイムラインに表示したいのですが、オーバーラップせずに画面の占有面積をできるだけ小さくしたいと考えています (マネージャーは各イベントをその四角形で表示し、その四角形で説明を表示したいため)。
上記の例の最適な配置は次のとおりです。
+-----+-----+
| A | C |
+---+-+-+---+
| D | E | B |
+---+---+---+
A と C は直線上にあり、D、E、B は別の直線上にあります。貪欲なアプローチでは、A と B を同じ行に配置し、C と D を別の行に配置し、E を 3 行目に配置します。