Skiena's Design on Algorithms.I の問題で立ち往生しています。私の解決策が正しいかどうかわかりません。
5-18。ムービーのセット M_1、M_2、..M_k を考えてみましょう。顧客のセットがあり、それぞれが今週末に見たい 2 つの映画を示しています。映画は土曜日の夜と日曜日の夜に上映されます。複数の映画が同時に上映される場合があります。どの映画を土曜日に放映し、どの映画を日曜日に放映するかを決定して、すべての顧客が希望する 2 つの映画を視聴できるようにする必要があります。各映画が最大 1 回上映されるスケジュールはありますか? そのようなスケジュールが存在する場合、そのようなスケジュールを見つけるための効率的なアルゴリズムを設計してください。
解決策: 映画用のセット {M1,M2..Mk} と、顧客用のセット {C1,C2,..Cp} があります。C1 が見たいエッジ 2 の映画に接続します。好きな映画2本を同じ夜に見せられなかった(好きな映画2本を色違いで色付け)など、二部グラフになっていないか検証したい.もしそうなら、私たちはすべての映画を土曜日に1番目の色で、日曜日に2番目の色で色付けして表示します.問題は解決しました.しかし、そうでない場合はどうすればよいですか?