¿Fusionar intervalos de tiempo superpuestos?

Question

I tienen las siguientes:

public class Interval 
{ 
    DateTime Start; 
    DateTime End; 
} 

I tienen un objeto List<Interval> que contiene múltiples intervalos. Estoy tratando de conseguir los siguientes (he usado los números para que sea fácil de entender):

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

Actualmente hago esto en Python de la siguiente manera:

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) 

pero estoy tratando de lograr lo mismo en C# (LINQ sería mejor pero opcional). ¿Alguna sugerencia sobre cómo hacer esto de manera eficiente?

Answer 1

Esto puede no ser la solución más bonita, pero puede funcionar tan bien

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; 
} 

Se apreciará cualquier regeneración.

Saludos

Answer 2

Este tipo de fusión normalmente se consideraría como un pliegue en los lenguajes funcionales. El equivalente LINQ es 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; 
} 

Hice la clase de intervalo genérico (Interval<T> where T : IComparable<T>), añade un método bool Contains(T value), y lo hizo inmutable, pero no tiene por qué cambiar mucho si desea utilizar la definición de clase como lo tienes ahora.

Answer 3

Aquí hay una versión que usa yield return - Me resulta más fácil de leer que haciendo una consulta Aggregate, aunque todavía es vago. Esto supone que ya ha ordenado la lista, de lo contrario, simplemente agregue ese paso.

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 4

Yo estaba acosada por el síndrome "No creé aquí" esta noche, así que aquí está el mío. El uso de un Enumerator me ahorró directamente un par de líneas de código, lo hizo más claro (IMO) y manejó el caso sin registros. Supongo que podría ejecutar una pizca más rápido también si se preocupan por eso ...

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); 
     } 
    } 
} 

En mi propia implementación, uso un tipo TimeRange para almacenar cada Tuple<DateTime, DateTime>, como sí lo hacen aquí. No lo incluí aquí simplemente para mantenerme enfocado/sobre el tema.

Answer 5

I utilizarse TimeRange como un contenedor de almacenamiento de los rangos:

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

    public DateTime start; 
    public DateTime end; 
} 

Se divide el problema en la combinación de dos intervalos de tiempo. Por lo tanto, el rango de tiempo actual (trabajo) coincide con los rangos de tiempo combinados previamente. Si uno de los intervalos de tiempo agregados previamente está desactualizado, se descarta y se utiliza el nuevo rango de tiempo (combinado del trabajo y el rango de tiempo coincidente). Los casos que descubierto para dos rangos() y [] son ​​como sigue:

1. []()
2. ([])
3. [(])
4. [()]
5. ([)]

6. () []

   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; 
   }