問題を解決しようとしていますが、残念ながら私の解決策はこのタスクに最適ではありません。
仕事：
パーティーには N 人のゲストがいます (0 < N < 30000 )。すべてのゲストは、いつパーティーに参加し、いつ退席するかを伝えます ([10;12] など)。タスクは、パーティーでできるだけ多くの人々の写真を撮ることです。1 枚の写真には 2 人 (ペア) しか写っていません。もちろん、写真は2人が同時にパーティーに参加している場合にのみ撮影できます。これは、出席間隔が重複する場合です。
私の考え：間隔から接続のグラフを作成するプログラムを書きました。グラフから接続数が最も少ない人を探します。つながりのある人の中から、つながりが最も少ない人も選びます。次に、これらの 2 つが写真のペアとして選択されます。どちらもグラフから削除されます。アルゴリズムは、接続がなくなるまで実行されます。
このアプローチは機能しますが、プログラムの計算には 10 秒の制限があります。1000 エントリでは 2 秒で実行されますが、4000 エントリでもかなりの時間がかかります。さらに、25000個のデータで試してみたところ、メモリ不足エラーでプログラムが停止し、接続を正しく保存することさえできません。
ここでは新しいアプローチが必要だと思いますが、これを機能させる他の方法が見つかりませんでした。
このタスクの適切なアルゴリズムを理解するのを手伝ってくれる人はいますか?
どうもありがとうございました！
サンプルデータ：
10
1 100
2 92
3 83
4 74
5 65
6 55
7 44
8 33
9 22
10 11
最初の行はゲストの数で、それ以降のデータはパーティーでの人の間隔です。