SQL or C#: Get all timespans without overlap

Question

Given a table with two DateTime columns (StartTime and EndTime), and rows with data which may overlap, how can I find a single instance of each combined start/end block?

For example, given:

07/01/2013 00:00:00, 07/01/2013 12:00:00
07/01/2013 06:00:00, 07/01/2013 18:00:00

I need a single result { 07/01/2013 00:00:00, 07/01/2013 18:00:00 }. The work can be done either in a SQL query, or in C# given a DataTable as described above.

Have you tried anything? We aren't here to write code for you. See **[FAQ: On-Topic](http://stackoverflow.com/help/on-topic)** — Michael Bray, Jul 09 '13 at 17:13
Like Michael Bray said, I'd suggest giving it a shot and having us help you tweak out any problems you're having. It's just an algorithmic problem, give it a shot and help us help you. — Tim, Jul 09 '13 at 17:15
Is it possible to have a 3rd event in the series such as this: 07/01/2013 15:00:00, 07/01/2013 22:00:00? Start time is after end time of first event? — Karl, Jul 09 '13 at 18:30

KeithS · Accepted Answer · 2013-08-19T23:24:26.197

The easiest way I can think of would be to slurp all records for the time range you're interested in, then "merge" records based on the well-known overlapping date formula:

List<Tuple<DateTime, DateTime>> dateRows = GetDateRowsSomehow();
//sorting by start time; you can do this in SQL pretty easily
//necessary to make sure the row most likely to overlap a given row is the next one
dateRows.Sort((a,b) => a.Item1.CompareTo(b.Item1));

for(var i=0; i<dateRows.Count - 1; i++)
    for(var j=i+1, j<dateRows.Count; j++)
        if(dateRows[i].Item1 <= dateRows[j].Item2
            && dateRows[i].Item2 >= dateRows[j].Item1) //overlap
        {
           //keep date row i, with the values of the complete time range of i and j
           dateRows[i].Item1 = dateRows[i].Item1 < dateRows[j].Item1
               ? dateRows[i].Item1
               : dateRows[j].Item1;
           dateRows[i].Item2 = dateRows[i].Item2 > dateRows[j].Item2
               ? dateRows[i].Item2
               : dateRows[j].Item2;
           //remove row j and ensure we don't skip the row after it
           dateRows.RemoveAt(j);
           j--;
        }

This solution's WCS is a large result set with zero overlap, which will perform on the order of N(N-1)/2 = O(N²). The best case is linear (not counting the NlogN sort operation or the repeated linear shifting within the List), when all rows in question have some overlap with each other. You can't use foreach because we're changing the size of the collection as we move through it. There is probably a more efficient way (for instance traversing the list back-to-front, minimizing shifting), but this should be decent, and also importantly, clean and concise.

score 1 · Answer 2 · answered Sep 13 '13 at 13:33

You can use the Time Period Library for .NET to calculate the time span without overlap:

// ----------------------------------------------------------------------
public void TimeSpansWithoutOverlap()
{
  // periods
  ITimePeriodCollection periods = new TimePeriodCollection();
  periods.Add( new TimeRange( 
    new DateTime( 2013, 7, 1, 0, 0, 0 ), 
    new DateTime( 2013, 7, 1, 12, 0, 0 ) ) );
  periods.Add( new TimeRange( 
    new DateTime( 2013, 7, 1, 6, 0, 0 ),
    new DateTime( 2013, 7, 1, 18, 0, 0 ) ) );

  ITimePeriodCollection combinedPeriods = new TimePeriodCombiner<TimeRange>().CombinePeriods( periods );
  foreach ( ITimePeriod combinedPeriod in combinedPeriods )
  {
    Console.WriteLine( "Period: " + combinedPeriod );
  }
} // TimeSpansWithoutOverlap

score 0 · Answer 3 · edited May 23 '17 at 11:49

0

As a starter, I would make a c# class and use DateTime operations to find the overlap. As for the overlap algorithm, just diff the start and end times.

Also seems to have done here Algorithm to detect overlapping periods

Also http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET

edited May 23 '17 at 11:49

Community

1
1

answered Jul 09 '13 at 17:22

jeffo

410
1
3
9

score 0 · Answer 4 · answered Jul 09 '13 at 17:34

Something like this ought to do you:

select *
from myTable t
where not exists ( select *
                   from myTable overlap
                   where overlap.partial_key = t.partial_key
                     and overlap.dateTimeFrom <= t.dateTimeThru
                     and overlap.dateTimeThru >= t.dateTimeFrom
                 )

It's a simple correlated subquery.

SQL or C#: Get all timespans without overlap

4 Answers4