How do I determine the maximum number of overlapping date ranges?
This question might be similar to:
- Determine if two date ranges overlap
- Comparing multiple date ranges to overlap: how to do it efficiently
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 valuesstart, +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 to share