0

日付範囲のリストがあります。

05/01/2012 - 07/01/2012
07/02/2012 - 09/05/2012
01/01/2012 - 03/31/2012
08/01/2012 - 12/31/2012

ここでの問題は、指定されたリストが特定の範囲内のすべての日付をカバーしているかどうかを確認することです。たとえば、このリストには 2012 年 5 月 1 日から 2012 年 12 月 31 日までのすべての日付が含まれますが、2012 年 1 月 1 日から 2012 年 12 月 31 日までの日付は含まれません。これは、4 月の日付がこのリストに含まれていないためです。仮定は、

  1. 日付範囲は有効です - 開始日 <= 終了日。
  2. 上記の 2 番目と 4 番目の場合のように、日付範囲が重複する場合があります。
  3. リストはソートされていません。

私がこれまでに持っているのは、外れ値を次のようにテストすることです。

最小の開始日と最大の終了日を見つける - テストの日付範囲の開始日と終了日がそれぞれこれらの日付よりも小さい/大きい場合、テストは失敗します。

しかし、途中で逃した日付をチェックするための最良の戦略は何ですか? 前もって感謝します！

4

5 に答える 5

3

最も簡単な戦略は、関連するすべての日付を解析することです。O(N)

日付を開始日で並べ替えます。 O(N log N)時間

終了日を次の開始日と比較します (過去にさかのぼる終了日は無視します)。O(N)

次の開始日までの 1 つの終了日が 1 日を超える場合は、ギャップがあります。

于 2013-01-07T20:42:04.543 に答える
2

最初に行うことは、入力データを修正することです。

  1. すべての範囲を開始日で並べ替える
  2. 開始日を設定して、すべての重複を取り除きます
  3. 2 によって消える範囲を削除します。

だからあなたの範囲は

01/01/2012 - 03/31/2012
05/01/2012 - 07/01/2012
07/02/2012 - 09/05/2012
09/06/2012 - 12/31/2012

次に、欠落している日付を見つける必要があります。その方法を理解できるかどうかを確認してください。

于 2013-01-07T20:44:02.167 に答える
0

日付を 1970 年 1 月 1 日 (または他の基準日) からの日数に変換します。

次に、問題は欠落している整数を見つけることになります。

于 2013-01-07T20:42:54.557 に答える
0

範囲内のすべての日付を生成し、それらをリストに入れて、候補者がそのリストに含まれているかどうかをテストします。

于 2013-01-07T20:42:58.240 に答える
0

次のようなことを試してください（リスト範囲を最小日付でソートした後）：-

  i=0
  a=min_date at 0 position
b=max_date corresponding to a

while list has elements
   c= min_date at (i+1) position
   d=max_date corresponding to c

if (b< (c - 1 day))
then there is a gap;
else 
{ 
if(b<d)   // done to handle the situation :- 06/07/2012 - 12/31/2012
          // 08/07/2012 - 11/31/2012. Then b will still remain 12/31/2012 after if condition
{
  b=d;
}
}
i=i+2;
end while;

上記は、リストにない日付のみを検索します。

于 2013-01-07T20:51:30.737 に答える