1

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 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--;
    }
}

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

Community
  • 1
  • 1
aleafonso
  • 2,244
  • 8
  • 38
  • 58
  • Do you mean "total number" by "maximum number" or may be the theoretical possible maximum number for a given number of ranges? – Olivier Jacot-Descombes Aug 14 '12 at 16:21
  • Maximum number. There are other 2 overlapping ranges, but I only care about the maximum number for this particular scenario – aleafonso Aug 14 '12 at 16:23
  • Now I know what you mean. You want to know the maximum number of ranges that overlap at the same date subrange. Here between 12/01 and 14/01 the three ranges (09/01-15/01), (11/01-20/01) and (12/01-14/01) do overlap. – Olivier Jacot-Descombes Aug 14 '12 at 16:37

1 Answers1

4
  • 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

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

AakashM
  • 62,551
  • 17
  • 151
  • 186