如何识别重叠的日期范围的最大值是多少？ [英] How to identify the maximum number of overlapping date ranges?

问题描述

此问题可能是相似的：

• 的确定是否两个日期范围重叠


• 的多个日期范围比较的重叠：如何有效地做到这一点

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

但是，我怎么能得到重叠的日期范围的最大值是多少？ （最好在C＃）

But, how can I get the maximum number of overlapping date ranges? (preferably in 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最大重叠的日期范围

Result = 3 maximum overlapping date ranges

解决方案：可能执行由@AakashM

Solution: Possible implementation of the solution proposed by @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 将并发日期范围的最大数量。

Where maxConcurrentCalls will be the maximum number of concurrent date ranges.

推荐答案

• 对于每一个范围，创建两个元组LT，日期时间，INT> s的值开始，+ 1 和结束， -1


• 按日期排序元组的集合


• 通过排序列表迭代，增加的数量部分元组运行总和，并通过运行总计


• 达到最大值的跟踪返回最大值的运行总计达到

• For each range, create two Tuple<DateTime, int>s with values start, +1 and end, -1
• Sort the collection of tuples by date
• Iterate through the sorted list, adding the number part of the tuple to a running total, and keeping track of the maximum value reached by the running total
• Return the maximum value the running total reaches

在执行为O（n log n）的，因为那种。有可能是一个更有效的方法。

Executes in O(n log n) because of the sort. There's probably a more efficient way.

这篇关于如何识别重叠的日期范围的最大值是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！