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?
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.
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.
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.
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.
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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With