11

要检查两个不同日期范围内的重叠，{Start1, End1}我{Start2, End2}正在检查：

if ((Start1 <= End2) && (End1 >= Start2))
{
  //overlap exists
}

问题是， 如果我有五个日期范围，那么比较重叠的好方法是什么？.

检查它们中的任何一个是否相互重叠？

如果我有多个日期范围，如何查找这些范围是否重叠？

4

6 回答 6

15

查找是否所有内容都重叠

static bool Overlap(params Tuple<DateTime, DateTime>[] ranges)
{
    for (int i = 0; i < ranges.Length; i++)
    {
        for (int j = i + 1; j < ranges.Length; j++)
        {
            if (!(ranges[i].Item1 <= ranges[j].Item2 && ranges[i].Item2 >= ranges[j].Item1))
                return false;

        }
    }
    return true;
}

查找是否有重叠

static bool Overlap(params Tuple<DateTime, DateTime>[] ranges)
{
    for (int i = 0; i < ranges.Length; i++)
    {
        for (int j = i + 1; j < ranges.Length; j++)
        {
            if (ranges[i].Item1 <= ranges[j].Item2 && ranges[i].Item2 >= ranges[j].Item1)
                return true;

        }
    }
    return false;
}
于 2011-02-06T00:57:31.187 回答
6

如果我理解正确，您想回答这个问题：这些范围中有两个重叠吗？将它们按照左端排序，然后查看1是否与2重叠，2是否与3重叠，等等。如果有重叠，这将找到它。我不相信有任何方法可以在不花费至少 O(n log n) 时间的情况下回答您的任意间隔列表的问题，这就是对它们进行排序的成本。

或者，也许您想回答这个问题：这些范围中是否有任何两个不重叠？（从表面上看，这就是您编辑的问题所要问的，但是（1）这似乎是一件奇怪的事情，（2）您上面的评论似乎表明这不是您的意思。）要检查这一点，请找到最左端的区间和最左端的区间，看它们是否重叠。（如果您的任何两个间隔不重叠，则这两个不重叠。）

于 2011-02-06T00:47:07.260 回答
2

尝试这个：

    private bool intersects(DateTime r1start, DateTime r1end, 
                            DateTime r2start, DateTime r2end)
    {
        return (r1start == r2start) 
            || (r1start > r2start ? 
                r1start <= r2end : r2start <= r1end);
    }
于 2011-08-04T14:10:32.423 回答
1 
   DateTime h1 = historyRecord.serviceStartDate;
   DateTime h2 = historyRecord.serviceEndDate;
   DateTime r1 = record.serviceStartDate;
   DateTime r2 = record.serviceEndDate;
   if (!((h1 > r1 && h1 > r2 && h2 > r1 && h2 > r2) || 
        (h1 < r1 && h1 < r2 && h2 < r1 && h2 < r2)))
       {
         count += 1;
       }
于 2011-05-24T19:56:30.730 回答
1

检查此算法以 简要检测重叠时段：

简单检查两个时间段是否重叠。

bool overlap = a.start < b.end && b.start < a.end;

或者在你的代码中......

bool overlap = tStartA < tEndB && tStartB < tEndA;
于 2017-08-23T10:15:56.557 回答
0

补充加雷斯的答案。对于需要在间隔中执行更复杂类型的重叠检查的任何人，有一个很好的数据结构，称为Interval Tree。

https://en.wikipedia.org/wiki/Interval_tree

树数据结构来保存间隔。具体来说，它允许人们有效地找到与任何给定区间或点重叠的所有区间。

取自此javascript 实现的示例

let tree = new IntervalTree();

let intervals = [[6,8],[1,4],[5,12],[1,1],[5,7]];

// Insert interval as a key and string "val0", "val1" etc. as a value 
for (let i=0; i < intervals.length; i++) {
    tree.insert(intervals[i],"val"+i);
}

// Get array of keys sorted in ascendant order
let sorted_intervals = tree.keys;              //  expected array [[1,1],[1,4],[5,7],[5,12],[6,8]]

// Search items which keys intersect with given interval, and return array of values
let values_in_range = tree.search([2,3])  //  expected array ['val1']
于 2020-05-15T03:34:29.830 回答