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

这个问题可能类似于：

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

但是，如何获得重叠日期范围的最大数量？ （最好是在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> myTupleList = new List<Tuple>(); foreach (DataRow row in objDS.Tables[0].Rows) // objDS is a DataSet with the date ranges { var myTupleFrom = new Tuple(DateTime.Parse(row["start_time"].ToString()), 1); var myTupleTo = new Tuple(DateTime.Parse(row["stop_time"].ToString()), -1); myTupleList.Add(myTupleFrom); myTupleList.Add(myTupleTo); } myTupleList.Sort(); int maxConcurrentCalls = 0; int concurrentCalls = 0; foreach (Tuple myTuple in myTupleList) { if (myTuple.Item2 == 1) { concurrentCalls++; if (concurrentCalls > maxConcurrentCalls) { maxConcurrentCalls = concurrentCalls; } } else // == -1 { concurrentCalls--; } } 

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

Answer 1

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

由于排序，在O(n log n)中执行。 可能有一种更有效的方式。