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

Question

这个问题可能类似于：

• 确定两个日期范围是否重叠
• 重叠的多个日期范围比较：如何有效地进行？

但是，我怎样才能获得重叠日期范围的最大数量？（最好在 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>带有值的 sstart, +1和end, -1
• 按日期对元组集合进行排序
• 遍历排序列表，将元组的数字部分添加到运行总计中，并跟踪运行总计达到的最大值
• 返回运行总计达到的最大值

O(n log n)由于排序而执行。可能有更有效的方法。