0

オープンまたはクローズのいずれかの単一の状態を持つ一連の入力日付が与えられ、少なくとも単一の入力日 (オープン状態) があり、結果として単一の日付 (クローズド、最大日付) が追加されて出力シーケンスが完成します。次に従う出力を生成するためにどのアルゴリズムを使用しますか?

1. 連続するオープン日および連続するクローズ日はありません。

2. オープン日ごとに、クローズ日が 1 つだけあります。

3. 最初の日付は Open で、最後の日付は Closed である必要があります。

4. 最初のオープン日と最後のクローズ日を除いて、各オープン日は前のクローズ日の直後、または別の言い方をすれば、各クローズ日は次のオープン日の前日でなければなりません。

5. 最終日は [Closed] と [Max date] (この例では 9999-12-31) です。

これは宿題ではありません。私はこれを C# で実装しました。これは、何百万回も実行される製品コードです。はい、パフォーマンスは重要ですが、可読性は非常に重要です。私が使用したアルゴリズムは完璧に機能しますが、見た目はひどいものです。どの言語でも大歓迎です。必要に応じて翻訳します。ありがとう。

例 1

input:
[2000-01-01,open] 

output: 
[2000-01-01,open]
[9999-12-31,closed]

例 2

input: 
[2000-01-01,open]
[2001-01-01,open]

output: 
[2000-01-01,open]
[2000-12-31,closed]
[2001-01-01,open]
[9999-12-31,closed]

例 3

input: 
[2000-01-01,open]
[2004-04-30,closed]

output: 
[2000-01-01,open]
[2004-04-30,closed]
[2004-05-01,open]
[9999-12-31,closed]

例 4

input: 
[2000-01-01,open]
[2000-03-17,open]
[2002-09-11,closed]
[2003-04-07,closed]

output: 
[2000-01-01,open]
[2000-03-16,closed]
[2000-03-17,open]
[2002-09-11,closed]
[2002-09-12,open]
[2003-04-07,closed]
[2003-04-08,open]
[9999-12-31,closed]

この種の問題を最もよく解決するのは、どのクラスの言語でしょうか?

4

3 に答える 3

5
  1. 入力を日付順に並べ替えます。
  2. 現在の状態を追跡しながら、入力を反復処理します。
  3. 状態がオープンで、オープン日が検出された場合は、クローズ日を挿入します。
  4. 状態がクローズで、クローズ日が検出された場合は、オープン日を挿入します。
  5. 状態がクローズで、前のクローズ日の翌日ではないオープン日が検出された場合は、オープン日とクローズ日を挿入してそのギャップを埋めます。
  6. 入力の反復処理が完了したら、状態がオープンの場合、最終クローズ日を挿入します。
  7. 入力の反復処理が完了したときに、状態がクローズであり、最終クローズ日が 9999-12-31 でない場合。最終的なオープン日とクローズ日を挿入します。
于 2012-08-29T13:34:57.863 に答える
0

最初にすべてのオープン日のリストを生成してから、最初のオープン日を除いてそれぞれから 1 日を引いてクローズ日を計算できます。

C# 擬似コード:

  var opendates = input.Select ( date =>
      date.Type == closing ? date.Date + 1day : date.Date
  ).Sort ();
  closingdates = opendates.Skip (1).Select (date => date - 1).Append ( new Date [] { 9999-12-31 } );
于 2012-08-29T13:32:52.043 に答える
0

ここではパフォーマンスが重要であるため、ソリューションは高速である必要があります。また、オンライン処理をサポートする必要があるため、システムの実行中にいつでも新しい開始/終了日を追加し、更新されたスケジュールをすぐに取得できます。

この問題の主な操作はソートであるため、ヒープを使用することをお勧めします。ヒープ内の各ノードには、日付と状態のペアが格納されます。アルゴリズムは空のヒープから開始し、読み取り入力として継続的に開発します。新しいデータが来ると、アルゴリズムはそれをツリーに挿入します。これには O(lgN) が必要です。スケジュールをプルする要求があると、アルゴリズムは O(N) かかる順序でトラバースを実行します。アルゴリズムは、パフォーマンスを向上させるために、時々バランスを取る必要があります。

于 2012-08-29T16:27:56.803 に答える