c# - 如何识别重叠日期范围的最大数量？

Question

这个问题可能类似于:

• Determine Whether Two Date Ranges Overlap
• Multiple Date range comparison for overlap: how to do it efficiently?

但是，我怎样才能获得重叠日期范围的最大数量？ (最好使用 C#)

示例:(从 - 到)

01/01/2012 - 10/01/2012
03/01/2012 - 08/01/2012
09/01/2012 - 15/01/2012
11/01/2012 - 20/01/2012
12/01/2012 - 14/01/2012

结果 = 3 个最大重叠日期范围

解决方案:@AakashM提出的解决方案的可能实现

List<Tuple<DateTime, int>> myTupleList = new List<Tuple<DateTime, int>>();

foreach (DataRow row in objDS.Tables[0].Rows) // objDS is a DataSet with the date ranges
{
    var myTupleFrom = new Tuple<DateTime, int>(DateTime.Parse(row["start_time"].ToString()), 1);
    var myTupleTo = new Tuple<DateTime, int>(DateTime.Parse(row["stop_time"].ToString()), -1);
    myTupleList.Add(myTupleFrom);
    myTupleList.Add(myTupleTo);
}

myTupleList.Sort();

int maxConcurrentCalls = 0;
int concurrentCalls = 0;
foreach (Tuple<DateTime,int> myTuple in myTupleList)
{
    if (myTuple.Item2 == 1)
    {
        concurrentCalls++;
        if (concurrentCalls > maxConcurrentCalls)
        {
            maxConcurrentCalls = concurrentCalls;
        }
    }
    else // == -1
    {
        concurrentCalls--;
    }
}

其中 maxConcurrentCalls 将是并发日期范围的最大数量。

Answer 1

• 为每个范围创建两个 Tuple<DateTime, int> s 的值为 start, +1和 end, -1
• 按日期对元组集合进行排序
• 遍历排序后的列表，将元组的数字部分添加到总计中，并跟踪总计达到的最大值
• 返回运行总和达到的最大值

在 O(n log n) 中执行因为排序。可能有更有效的方法。