単一の入力日付の任意のシリーズを考えるOpenまたはClosedの状態。最低でも単一の入力日付（open state）があり、単一の日付（Closed、max Date）が追加されて出力シーケンスを完了します。どのアルゴリズムを使用して出力を生成しますか。以下に従いますか？
1.連続したオープン日と連続したクローズ日はありません。
2.開始日ごとに1つの終了日があります。
3.最初の日付はオープンで、最後の日付はクローズする必要があります。
4。 最初のオープン日と最後のクローズ日とは別に、各オープン日は直前のクローズ日に従うか、別の言い方をすれば、各クローズ日は次のオープン日の前日でなければなりません。
5.最終日は、終了日と最大日（この例では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]
どのクラスの言語がこの種の問題を最もよく解決するかを尋ねますか？
回答：
回答№1は5- 入力を日付でソートします。
- 入力を反復処理して、現在の状態を追跡します。
- 状態が開いており、開いている日付が見つかった場合は、閉じた日付を挿入します。
- 状態が閉じられ、閉じられた日付が検出された場合、開いている日付を挿入します。
- 状態が閉じられ、前の閉じられた日付の翌日ではない開いている日付が検出された場合、開いている日付と閉じられた日付を挿入して、そのギャップを埋めます。
- 入力の反復処理が完了し、状態が開いている場合は、最終的な終了日を挿入します。
- 状態が閉じられていて、最終的な閉じられた日付が9999-12-31でない場合、入力の繰り返し処理が完了したとき。最終オープン日とクローズ日を挿入します。
回答№2の場合は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 } );
回答№3の場合は0
そのため、パフォーマンスはここで重要です。また、オンライン処理をサポートする必要があるため、システムの実行中にいつでも新しい開始/終了日を追加して、すぐに更新されたスケジュールを取得できます。
この問題の主要な操作はソートするには、ヒープを使用することをお勧めします。ヒープ内の各ノードには、日付/状態のペアが格納されます。アルゴリズムは空のヒープで開始し、読み取り入力として継続的に開発します。新しいデータが到着すると、アルゴリズムはそれをツリーに挿入し、O（lgN）を取得します。スケジュールをプルする要求があると、アルゴリズムはO（N）を取得する順序走査を実行します。また、アルゴリズムは、パフォーマンスを向上させるために時々バランスをとる必要があります。