0

イベントのデータ セット (開始日、終了日、場所) があります。これらのイベントは国内で移動するため、どのイベントが終了したらどこに行くべきかを把握する必要があります。

例:

  1. [1/7, 6/7, トロント] (7月1日開始、7月6日終了)
  2. [2/7、4/7、モントリオール]
  3. [4/7、11/7、オタワ]
  4. [17/7、22/7、バンクーバー]

..etc (データセットは約 100 エントリになるため、パフォーマンスは実際には問題になりません)

この例では、イベント 1 は 7 月 6 日に終了し、イベント 4 は 17 日に開始されるため、移動してイベント 4 を実行できます。（当日乗り継ぎ前提）

適切な一致を見つけることができなかったすべてのイベントは、誰かが手動で一致させるためにレポートに保存されます。

この最適化コードは JavaScript で実行されます。

私の最初の考えは、同じデータを持つ2つの配列を持つことでした。最初の配列は開始日でソートされ、2 番目の配列は終了日でソートされます。次に、終了日のリストを調べて、適切な開始日を見つけようとします。次に、これらのエントリを配列から削除し、一致しなくなるまで同様に続けます。

この問題にアプローチする方法について、より良いアイデアを持っている人はいますか? 詳細が必要な場合はお知らせください。

4

1 に答える 1

1

あなたの質問はあまり明確ではありません。私の理解が正しければ、あなたの目標は、選択によってイベントの数が最大になるようにイベントのサブセットを選択することです (イベントが重複しないようにします)。もしそうなら、あなたの問題は活動選択の問題として見ることができます。それを解決するための単純な貪欲なアルゴリズムがあります。

させて

event[1..n] the n events
start[i] the start time of the event number i
finish[i] the finish time of the event number i

イベントを終了時間でソート済みであると仮定します。

次の貪欲なアルゴリズムは、重複しないイベントの最大のサブセットSを見つけます: ( lseはLast Selected Eventであることに注意してください)

S = {event[1]}
lse = 1

foreach event[i] do:
     if start[i] > finish[lse]:
         S = S + {event[i]}
         lse = i

return S

基本的：

  1. イベントを終了時刻で並べ替えます
  2. 最初のイベントを選択します
  3. イベントをループし、最後に選択したイベントと重複しない最初のイベントを貪欲に選択します
于 2012-07-13T21:38:33.700 に答える