そこで、可能な限り少ない数の教室を使用して重複する可能性のある n 個のアクティビティをスケジュールするという問題の解決策に関して、いくつか質問があります。解決策は次のとおりです。
一連のアクティビティ S をスケジュールするための教室の最小数を見つけます。これを行うには、開始時間と終了時間に従ってアクティビティを効率的に進めます。教室の 2 つのリストを維持します: 時間 t に使用中の部屋と時間 t に空いている部屋です。t がアクティビティの開始時刻になったら、このアクティビティを空いている部屋にスケジュールし、その部屋をビジー リストに移動します。同様に、アクティビティが停止したら、部屋を空きリストに移動します。最初はゼロ部屋から始めます。フリー リストにルームがない場合は、新しいルームを作成します。
アルゴリズムは、アクティビティを並べ替えることで実装できます。開始時間または終了時間ごとに、アクティビティをスケジュールし、一定の時間内にリスト間で部屋を移動できます。したがって、合計時間はソートによって支配されるため、O(n lg n) になります。
私の質問は
1) まず、開始時刻と終了時刻を同時に行うことで、活動をどのように進めますか?
2) リスト間で一定時間内に部屋を移動する方法がよくわかりません。部屋をビジー リストから空きリストに移動したい場合、ビジー リスト内のすべての部屋を反復処理して、終了時刻が過ぎている部屋を確認する必要はありませんか?
3）これを機能させるために追跡する必要がある「状態」変数はありますか？