わかりました、私はこれに適切なコードで答えるつもりはありません。問題について私が理解していることを定義しようとするので、せいぜい疑似コードしかありません。また、浮動小数点時間ではなく整数時間を使用すると仮定しますが、結局のところ、大きな違いはないと確信しています。
ここでの貪欲な解決策は、単に無料の講堂に割り当て、以前に使用された講堂を常に使用することです。つまり、ソリューションがあなたに何を求めているのか、私は確信しています。
したがって、最初に、すべての「イベント」を保持するある種のstructorを作成classします。ここで、「イベント」をアクティビティの開始時間または終了時間として定義します。このstruct/classは、開始/終了時間であったアクティビティへの参照も保持します。
多分ちょっと好きです（C++構文の方が簡単で、私は怠け者だからです）：
struct evt
{
int activityID;
int time;
bool isStart;
};
struct次のステップは、これまたは各アクティビティの開始/終了時間のインスタンスを構築し、classそれをある種のリスト データ構造に配置することです (これが C++ の場合は、 を使用しvector、Java の場合と推測ArrayListします)。次に、に基づいてイベントを並べ替えますtime。したがって、Java の場合、時間に基づいてこれらのイベントの順序を決定する何らかの比較関数が必要になります。また、コンパレーター内では、開始イベントであるイベントは、終了イベントであるイベントよりも遅くなります (間隔が半分開いていることを思い出してください)。ArrayList「 」と呼びますeventList。
次に、 nホール (すべてのアクティビティを実行するには最大でnホールが必要) であると私が想定する 2 つのリストがあります。1 つのリストにすべてのホールが含まれています。使用されていないホールの一覧です。他のリストは空です。これは、使用中のホールのリストになります。これらは、前面から削除できるリストになります (JavaArrayListはこれを実行できると思います)。
各アクティビティをホールに割り当てることができるように、ホールを特定する何らかの方法と、おそらくある種の参照配列が必要です。この部分は少し不明確であり、実装の詳細はあなたに任せたいと思いますが、もしnが大きすぎなければ、おそらく (C++ で)vector<int>サイズnの aとそのi番目の要素を持つでしょう。vectorホール識別子になるか、-1まだ割り当てられていない場合。これを Java で試した場合、これはint[n]配列になります。
次に、 を反復処理しeventList、各イベントで、それが終了時間か開始時間かを確認します。開始時間であれば、「空きホール」リストの先頭要素を「使用中」のホールに入れます。終了時間だったら、終わったばかりのホールを「使用中」リストから外して、「空きホール」リストの先頭に戻します。前に説明した参照配列も更新する必要があることを思い出してください。
最後に、少し手を加えると、使用されたホールの数がわかりました。ホールを使用していたときに実行されていたアレイまたはカウンターを介した線形パスで十分でした. うまくいくと思う 1 つの方法は、一度に使用されているホールの数を保持するリストの最大サイズを記録することですが、これは正しくない可能性があります (十分にテストしていません)。
私は頭のてっぺんからこれをやっているだけなので、この解決策はおそらく現時点では少し混乱しています。申し訳ありません。ここで要約してみます：
- 開始・終了時刻をイベントとしてまとめたクラスを宣言する
- すべての開始時刻と終了時刻を配列に並べ替えます。早い時刻はリストの前に、終了時刻は開始時刻の前に表示されます
- ホールのリストを作成し、使用されているすべてのホールになる別の (空のリスト)
- 各イベントを処理し、開始時刻の場合はホールを使用中リストに移動し、終了時刻の場合は空きリストにホールを移動します
これは非常に長い投稿であり、多くのコードを提供していないため (ヒントを落としてみましたが、役に立ったかどうかはわかりません)、さらに質問がある場合はお知らせください。できる。
ここで見られる「アクティビティの選択」の問題は、常に最も早く終了するアクティビティを選択することによって、貪欲な方法で解決できます。これは少し違うと思いますが、興味深いかもしれないので含めました。