How do I determine the maximum number of overlapping date ranges?

This question might be similar to:

But how can I get the maximum number of overlapping date ranges? (preferably in C #)

Example: (from - to)

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

      

Result = 3 maximum overlapping date ranges

Solution : Possible implementation of the solution suggested 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--;
    }
}

      

Where maxConcurrentCalls

will be the maximum number of concurrent date ranges.

+1


source to share


1 answer


  • For each range, create two Tuple<DateTime, int>

    with values start, +1

    andend, -1

  • Sorting a collection of tuples by date
  • Iterate through a sorted list, adding the part number of the tuple to the grand total and keeping track of the maximum value reached with the grand total
  • Returns the maximum value reached in the current period.


Executed in O(n log n)

due to sorting. This is probably a more efficient way.

+3


source







All Articles