用于验证间隔列表的算法

Algorithm to validate a list of intervals

本文关键字：算法 列表 验证 用于      更新时间：2023-09-26

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

  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/史蒂夫

这段代码提供了一个解决方案，尽管我假设以下内容：

  • 您不介意对列表进行排序。它大大减少了比较次数要做。
  • 根据您的示例，日期之间的比较是按天级别进行的。如果没有，您可能需要更改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]));
}

首先使用类似的东西解析日期python中的datetime.datetime.strptime和将日期转换为毫秒并进行简单的检查。

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

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

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

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

相关文章：