0

開始日と終了日を含むプロジェクトのリストがあるとします。また、さまざまな週の範囲もあります (月、年など)。週ごとに 4 つの値を示すグラフを表示したいと思います。

  1. プロジェクト開始
  2. プロジェクトは終了しました
  3. 総プロジェクト開始数
  4. クローズしたプロジェクトの合計

週ごとの値の範囲をループし、各週についてプロジェクトのリストを繰り返し処理し、これらの 4 つのトレンドの値を 1 週間ごとに計算することができます。これにはアルゴリズムの複雑さがありO(nm)、nは週のリストのm長さ、 はプロジェクトのリストの長さです。それはそれほど素晴らしいことではありません。より効率的なアプローチはありますか? もしそうなら、それは何でしょうか?

関係がある場合は、Java でコーディングしています

4

3 に答える 3

3

「プロジェクト」と「合計」の違いが何であるかはわかりませんが、各週に開始および終了したプロジェクトの数を計算する簡単な O(n log n) の方法を次に示します。

  1. プロジェクトごとに、その開始点と終了点をリストに追加します。
  2. リストを昇順に並べ替えます。
  3. 後の週に発生する時点に到達するまで、リストをたどって時点を引き出します。この時点で、「開始されたプロジェクト」はヒットした開始点の総数であり、「終了したプロジェクト」はヒットした終了点の総数です。これらのカウンターを報告し、両方をゼロにリセットします。その後、翌週の処理に進みます。

ちなみに、開始または終了するプロジェクトがない週が数週間ある場合、この手順はそれらをスキップします。これらの週を「0, 0」の合計として報告したい場合、ゼロ以外の合計を含む週を出力するときはいつでも、最初に「0, 0」の週を出力してからのギャップを埋めるのに必要なだけの数を出力するようにしてください。過去のゼロ以外の合計週。lastNonzeroWeek(これは、ゼロ以外の合計週を出力するたびに変数を設定するだけで簡単に実行できます。)

于 2014-10-30T15:58:54.847 に答える