5

以下を行うアルゴリズムを探しています。重複する可能性のある期間にまたがるイベントのタイムラインがあります。これらのイベントを、それぞれが 1 つ以上のイベントの存在によって定義される、重複しない単一のタイムライン期間にまとめたいと思います。

概念的には単純ですが、考えられるすべてのケースを把握してタイムラインを適切に分割するのは少し面倒な場合があります。

説明すると（ここでは横軸は時間です）：

Event A   -----
Event B      ----

になる

Event A   ---
Event A+B    --
Event B        --

もう一つの例：

A    -----------
B       ---
C            --

なる:

A    ---
A+B     ---
A          --
A+C          --
A              -

これを行うための標準的なアルゴリズム/データ構造はありますか?

4

1 に答える 1

5

すべてのイベントの開始時刻と終了時刻を配列に入れ、それらを時間の減少しない順序で並べ替えます (「開始」と「終了」が同時に発生した場合は、「終了」を最初に配置して同点を解消します) .

スイープ ラインアルゴリズムを実行します。

「アクティブな」イベントのセットを維持しながら、ソートされた配列を走査します。あなたのソリューション。

結果の一連のイベントはバラバラで、必要に応じてラベルを付けることができます。

于 2013-03-29T19:24:14.940 に答える