2

重複する可能性のある（日付）間隔がたくさんあります。間隔はさまざまなソースから取得されます。この「タイムライン」を「平坦化」してから、間隔がなかったすべての間隔を見つけたいと思います。

http://www.dgp.toronto.edu/people/JamesStewart/378notes/22intervals/ の「より複雑な例」セクションを参照してください。したがって、作曲家が生きていなかった区間を見つけたいと思います。

それ、どうやったら出来るの？そして、PHPでそのようなことをどのように実装しますか? PHP には、ツリーを構築するための簡単な関数もありますか?

多くのthx！

編集 私の入力は、次のような開始日と終了日を含むいくつかの配列 (2、3、または 4) です。

 $myarray1[0]['start']['date'] = 'somedate'
 $myarray1[0]['stop']['date'] = 'somedate'
 $myarray1[1]['start']['date'] = 'somedate'
 $myarray1[1]['stop']['date'] = 'somedate'
 $myarray1[2]['start']['date'] = 'somedate'
 $myarray1[2]['stop']['date'] = 'somedate'

同じことが myarray2、myarray3 などにも当てはまります。

4

2 に答える 2

3

基本アルゴリズム

コンポーザーごとに、2 つのオブジェクトを作成します。1 つは、作曲者の名前と生年月日を含む誕生オブジェクトです。もう 1 つは死亡オブジェクトで、これも作曲者の名前と死亡年が表示されています。

これらのオブジェクトを一緒に並べ替えます。

forintに初期化された を保持します。0num_composers_alive

オブジェクトの順序付きリストを反復処理します。出生オブジェクトに遭遇するたびに、 をインクリメントしますnum_composers_alive。死亡オブジェクトに遭遇するたびに、デクリメントしますnum_composers_alive。

インクリメントまたはデクリメント中に、死亡およびデクリメントをヒットするたびに、num_composers_alive0 になったかどうかを確認します。そうであれば、作曲家が生きていない期間に入っただけです。その数値を出力するか、どこかに保存します。出生と増分をヒットするたびに、num_composers_alive現在 1 かどうかを確認します。そうである場合は、作曲家が生きていなかった期間を終えたばかりです。その数値を出力するか、どこかに保存します。

実装

これは、入力と出力の形式によって異なります。PHP にツリーのネイティブな概念があるとは思いませんが、それについては間違っているかもしれません。上記を実装してみて、行き詰まった場合は別の質問を開いてください。

正直なところ、上記の問題を解決するためにツリーが必要な理由はわかりませんが、おそらくそれは別の目的のためです。

于 2012-09-12T13:57:49.323 に答える
1

段階的な単純なアルゴリズム

  1. 日付オブジェクトを整数に変換する関数を定義します (逆も同様です)。これは、すべての数値をできるだけ小さくするために変換を最適化する必要がある場合がある場所です。過去の日付は、未来の日付よりも小さい数値でなければなりません

  2. 数値の配列を初期化します。すべてのビットを に設定します0。配列のサイズが最大の日付番号 (ステップ 1 から) と一致していることを確認してください。

  3. 日付範囲を繰り返す

  4. 配列内の日付範囲を1s でマークします。数値に変換された日付 (手順 1) を配列内のインデックスとして使用します。

  5. sを含むすべてのインデックスを0日付間隔に戻します。

ランタイムの複雑さ O(N)。スペースの複雑さ O(N)。

于 2012-09-12T17:17:22.603 に答える