Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Merging overlapping time intervals?

Tags:

c#

linq

I have the following:

public class Interval
{
   DateTime Start;
   DateTime End; 
}

I have a List<Interval> object containing multiple intervals. I am trying to achieve the following (I used numbers to make it easy to understand):

[(1, 5), (2, 4), (3, 6)] --->  [(1,6)]
[(1, 3), (2, 4), (5, 8)] --->  [(1, 4), (5,8)]

I currently do this in Python as follows:

def merge(times):
    saved = list(times[0])
    for st, en in sorted([sorted(t) for t in times]):
        if st <= saved[1]:
            saved[1] = max(saved[1], en)
        else:
            yield tuple(saved)
            saved[0] = st
            saved[1] = en
    yield tuple(saved)

but am trying to achieve the same in C# (LINQ would be best but optional). Any suggestions on how to do this efficiently?

like image 767
Legend Avatar asked Jul 14 '12 00:07

Legend


People also ask

How do you merge overlapping intervals?

A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from the list and merge the other into the first interval. Repeat the same steps for the remaining intervals after the first.

What is an overlapping interval?

Let's take the following overlapping intervals example to explain the idea: If both ranges have at least one common point, then we say that they're overlapping. In other words, we say that two ranges and are overlapping if: On the other hand, non-overlapping ranges don't have any points in common.

What are merge intervals?

The Merge Intervals Problem intervals is a 2 dimensional list, with each nested list representing an interval. The function merges all overlapping intervals in intervals and returns the merged intervals.

How do you find overlapping time intervals in SQL?

Basically, a period can be represented by a line fragment on time axis which has two boundaries; starttime and endtime. To claim two time periods to be overlapping, they must have common datetime values which is between lower and upper limits of both periods.


1 Answers

Here's a version using yield return - I find it easier to read than doing an Aggregate query, although it's still lazy evaluated. This assumes you've ordered the list already, if not, just add that step.

IEnumerable<Interval> MergeOverlappingIntervals(IEnumerable<Interval> intervals)
{
  var accumulator = intervals.First();  
  intervals = intervals.Skip(1);

  foreach(var interval in intervals)
  {
    if ( interval.Start <= accumulator.End )
    {
        accumulator = Combine(accumulator, interval);
    }
    else
    {
        yield return accumulator;
        accumulator = interval;     
    }       
  }

  yield return accumulator;
}

Interval  Combine(Interval start, Interval end)
{
  return new Interval 
  {
    Start = start.Start,
    End = Max(start.End, end.End),
  };
}

private static DateTime Max(DateTime left, DateTime right) 
{
    return (left > right) ? left : right;
}
like image 77
Paul Phillips Avatar answered Nov 06 '22 04:11

Paul Phillips