重叠的多个日期范围比较:如何有效地进行？

Question

要检查重叠,在两个不同的dateranges,{Start1, End1}和{Start2, End2}我检查:

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

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

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

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

Answer 1

找出是否所有都重叠

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;
}

Answer 2

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

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