Merging overlapping time slots?

Question

I have the following:

public class Interval { DateTime Start; DateTime End; } 

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

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

I am currently doing 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 I'm trying to do the same in C # (LINQ would be better, but not necessary). Any suggestions on how to do this efficiently?

Answer 1

Here's a version using yield return — it's easier for me to read than making an Aggregate request, although it's still lazy. This assumes you have already ordered the list, if not, just add this 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; } 

Answer 2

It may not be the prettiest solution, but it may work as well.

 public static List<Interval> Merge(List<Interval> intervals) { var mergedIntervals = new List<Interval>(); var orderedIntervals = intervals.OrderBy<Interval, DateTime>(x => x.Start).ToList<Interval>(); DateTime start = orderedIntervals.First().Start; DateTime end = orderedIntervals.First().End; Interval currentInterval; for (int i = 1; i < orderedIntervals.Count; i++) { currentInterval = orderedIntervals[i]; if (currentInterval.Start < end) { end = currentInterval.End; } else { mergedIntervals.Add(new Interval() { Start = start, End = end }); start = currentInterval.Start; end = currentInterval.End; } } mergedIntervals.Add(new Interval() { Start = start, End = end }); return mergedIntervals; } 

Any feedback would be appreciated.

Hi

Answer 3

Today I was stopped by the "Not Created Here" syndrome, so here's mine. Using Enumerator directly saved me a couple of lines of code, made them clearer (IMO), and handled the case without writing. I suppose this could lead to smidge being faster if you like it ...

 public IEnumerable<Tuple<DateTime, DateTime>> Merge(IEnumerable<Tuple<DateTime, DateTime>> ranges) { DateTime extentStart, extentEnd; using (var enumerator = ranges.OrderBy(r => r.Item1).GetEnumerator()) { bool recordsRemain = enumerator.MoveNext(); while (recordsRemain) { extentStart = enumerator.Current.Item1; extentEnd = enumerator.Current.Item2; while ((recordsRemain = enumerator.MoveNext()) && enumerator.Current.Item1 < extentEnd) { if (enumerator.Current.Item2 > extentEnd) { extentEnd = enumerator.Current.Item2; } } yield return Tuple.Create(extentStart, extentEnd); } } } 

In my own implementation, I use the TimeRange type to store each Tuple<DateTime, DateTime> , as the other does. I did not include this here just to focus / on topic.

Answer 4

Such a merger is usually regarded as a fold in functional languages. Equivalent to LINQ Aggregate .

 IEnumerable<Interval<T>> Merge<T>(IEnumerable<Interval<T>> intervals) where T : IComparable<T> { //error check parameters var ret = new List<Interval<T>>(intervals); int lastCount do { lastCount = ret.Count; ret = ret.Aggregate(new List<Interval<T>>(), (agg, cur) => { for (int i = 0; i < agg.Count; i++) { var a = agg[i]; if (a.Contains(cur.Start)) { if (a.End.CompareTo(cur.End) <= 0) { agg[i] = new Interval<T>(a.Start, cur.End); } return agg; } else if (a.Contains(cur.End)) { if (a.Start.CompareTo(cur.Start) >= 0) { agg[i] = new Interval<T>(cur.Start, a.End); } return agg; } } agg.Add(cur); return agg; }); } while (ret.Count != lastCount); return ret; } 

I made the generic Interval class ( Interval<T> where T : IComparable<T> ), added the bool Contains(T value) method and made it immutable, but you don't need to change it much if you want to use the class definition the way it is there is now.

Answer 5

I used TimeRange as a container storing ranges:

 public class TimeRange { public TimeRange(DateTime s, DateTime e) { start = s; end = e; } public DateTime start; public DateTime end; } 

He divides the problem by combining two time ranges. Therefore, the current time range (operation) is consistent with previously combined time ranges. If one of the previously added time ranges is out of date, it is discarded and a new time range is used (combined with the work and the matching time range). The cases that I found out for the two ranges () and [] are as follows:

• [] ()
• ([])
• [(])
• [()]
• ([)]

• () []

   public static IEnumerable<TimeRange> Merge(IEnumerable<TimeRange> timeRanges) { List<TimeRange> mergedData = new List<TimeRange>(); foreach (var work in timeRanges) { Debug.Assert(work.start <= work.end, "start date has to be smaller or equal to end date to be a valid TimeRange"); var tr = new TimeRange(work.start, work.end); int idx = -1; for (int i = 0; i < mergedData.Count; i++) { if (tr.start < mergedData[i].start) { if (tr.end < mergedData[i].start) continue; if (tr.end < mergedData[i].end) tr.end = mergedData[i].end; } else if (tr.start < mergedData[i].end) { tr.start = mergedData[i].start; if (tr.end < mergedData[i].end) tr.end = mergedData[i].end; } else continue; idx = i; mergedData.RemoveAt(i); i--; } if (idx < 0) idx = mergedData.Count; mergedData.Insert(idx, tr); } return mergedData; }