1

開始/終了日時の値のリストを考えると、次の3つのことを検証する必要があります。

  1. 各間隔で、開始時刻は終了時刻より前です
  2. リスト要素間に重複は存在しません。各開始/終了スパンは、リスト全体の離散間隔を表す必要があります
  3. シリーズにギャップはあり得ません。最初から最後まで、継続的にカバーする必要があります。

だから、与えられた：

( (1970-01-01, 1970-12-31), (1971-01-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31) )

成功の結果が示されます。

与えられた

( (1970-12-31, 1970-01-01), (1970-10-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31) )

開始日が最初の要素の終了日より後に来ることを示すメッセージが提供されます。

与えられた

( (1970-01-01, 1970-12-31), (1970-10-01, 1971-12-31), (1972-01-01, 1972-12-31), (1973-01-01, 1973-12-31) )

最初の要素と2番目の要素の間に重複が存在することを示すメッセージが提供されます。

与えられた

( (1970-01-01, 1970-12-31), (1971-10-01, 1971-12-31), (1973-01-01, 1973-12-31), (1974-01-01, 1974-12-31) )

2番目と3番目の要素の間にギャップが存在することを示すメッセージが提供されます。

最初の要件は単純なものです。問題は、より広範な検証にどのように組み込むのが最適かということです。

2番目の要件は、以下の記事である程度満たされていますが、1組の間隔でしか機能しないため、各要素を他のすべての要素と比較する必要があるため、O（n ^ 2）を実現します。2つの日付範囲が重複しているかどうかを判断する

この記事-間隔のリストで間隔の重複を検索しますか？-2番目の要件により適切に対処しているようで、最初の要件は区間木の母集団に組み込むことができます。

したがって、3番目の要件が残ります。区間木を使用して、区間全体のギャップを決定することは可能ですか？

これはJavascript、node.jsにあることをお伝えします。ただし、これをHaskellまたは別の関数型言語で解決するのは興味深いでしょう...

ありがとう！

r/スティーブ

4

3 に答える 3

1

このコードは解決策を提供しますが、私は次のことを想定しています。

  • リストがソートされていてもかまいません。これにより、実行する比較の数が大幅に削減されます。
  • 例を使用すると、日付間の比較は日レベルで行われます。そうでない場合は、おそらくstrToDate関数とadjustment変数を変更する必要があります。

アイデアは@alfasinから取られました。

var data = [
    ['1970-01-01', '1970-12-31'], 
    ['1971-01-01', '1971-12-31'], 
    ['1972-01-01', '1972-12-31'], 
    ['1973-01-01', '1973-12-31']
];

// comparison is in day level, adjust otherwise.
var adjustment = 1000 * 60 * 60 * 24;

var parsedData = [];
for(var idx = 0; idx < data.length; idx++) {
    var thisItem = data[idx];

    var thisParsedItem = [
        Math.floor(strToDate(thisItem[0]).getTime() / adjustment), 
        Math.floor(strToDate(thisItem[1]).getTime() / adjustment),
        // adding original items here, since I plan to sort the list.
        thisItem[0],
        thisItem[1]
    ];

    parsedData.push(thisParsedItem);
}

parsedData = parsedData.sort(function (itemA, itemB) {
    return itemA[0] - itemB[0];
});


var errorLocation = -1, overlap = false, gap = false, endBeforeStart = false;
for(var idx = 0; idx < parsedData.length - 1; idx++) {
    // start before end.
    if (parsedData[idx][0] > parsedData[idx][1]) {
        errorLocation = idx;
        endBeforeStart = true;
        break;
    }

    var d = parsedData[idx + 1][0] - parsedData[idx][1];

    // gap.
    if (d > 1) {
        errorLocation = idx + 1;
        gap = true;
        break;
    }

    // overlap.
    if (d < 1) {
        errorLocation = idx + 1;
        overlap = true;
        break;
    }
}

if (errorLocation > -1) {
    if (gap) { console.log("You have a gap at: " + errorLocation); }
    if (overlap) { console.log("You have an overlap at: " + errorLocation); }
    if (endBeforeStart) { console.log("End before start at: " 
                                  + errorLocation); }
}

function strToDate(input) {
    var parts = input.split('-');
    return new Date(
            parseInt(parts[0]), 
            parseInt(parts[1]), 
            parseInt(parts[2]));
}
于 2012-06-29T02:29:31.843 に答える
0

完全に機能する例を提供せずに、次のことを行うことができます。

  1. 開始日でリストを並べ替えます（並べ替え機能では、次の場合にも検証できますstart < end）
  2. リストを繰り返し処理し、次のいずれかを確認します。
    1. itemはリストの最初のアイテムです
    2. 開始日が前の停止日より1つ多い

ただし、関数が既にソートされていて、手順1をスキップできない限り、これによって関数の順序が実際に下がることはないと思います（N x N log N）。

于 2012-06-29T01:31:34.413 に答える
0

Pythonでdatetime.datetime.strptimeのようなものを使用して最初に日付を解析し、日付をミリ秒に変換して、簡単なチェックを行います。

Pythonで現在の時刻をミリ秒単位で取得しますか？

于 2012-06-29T01:25:52.197 に答える