1

给定开始/结束日期时间值的列表，我需要验证三件事：

  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) )

提供说明第一和第二元素之间存在重叠的消息。

给定

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

提供一条消息，说明第二个和第三个元素之间存在间隙。

第一个要求很简单，问题是如何最好地将其纳入更广泛的验证。

下面的文章在一定程度上满足了第二个要求，但由于它仅适用于一对间隔，我仍然会意识到 O(n^2) 因为每个元素都需要与其他元素进行比较，对吗？确定两个日期范围是否重叠

这篇文章 -在区间列表中搜索区间重叠？- 似乎更好地解决了第二个要求，第一个可以滚动到区间树的种群中。

这样就剩下第三个要求了。是否可以使用区间树确定整个区间的间隙？

我会提到这是在 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

首先使用 python 中的 datetime.datetime.strptime 之类的解析日期，然后将日期转换为毫秒并进行简单的检查。

在 Python 中以毫秒为单位获取当前时间？

于 2012-06-29T01:25:52.197 回答
0

如果不提供完整的工作示例，您可以执行以下操作：

  1. 按开始日期对列表进行排序（在排序功能中，您还可以验证 if start < end）
  2. 遍历列表并确保：
    1. item 是列表的第一项
    2. 开始日期比上一个停止日期多一个

我想这并没有真正降低函数的顺序（N x N log N），除非它已经排序并且您可以跳过第 1 步。

于 2012-06-29T01:31:34.413 回答