合併重疊時間間隔？

Question

我有以下：

public class Interval 
{ 
    DateTime Start; 
    DateTime End; 
} 

我有包含多個間隔List<Interval>對象。我想實現如下（我用的數字，這樣才容易理解）：

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

我目前做這在Python如下：

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) 

但想實現在同一C＃（LINQ將是最好的，但可選）。有關如何有效地做到這一點的任何建議？

Answer 1

這可能不是最漂亮的解決方案，但它可能工作以及

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

任何反饋將不勝感激。

Regards

Answer 2

這種合併通常被認爲是功能語言中的摺疊。 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; 
} 

我所做的間隔類通用（Interval<T> where T : IComparable<T>），增加了一個bool Contains(T value)方法，並使其不可變的，但如果你想，你現在有它使用的類定義，你應該不需要太多改變它。

Answer 3

這是一個使用yield return的版本 - 我發現它比查詢Aggregate更容易閱讀，儘管它仍然被惰性評估。這假定你已經訂購了該列表，如果沒有，只需添加該步驟即可。

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

我被今晚的「未創建」綜合徵困擾，所以這裏是我的。使用枚舉器直接爲我節省了幾行代碼，使其更清晰（IMO），並處理沒有記錄的案例。我想它可能運行更快微幅下挫，以及如果你關心的是......

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

在我自己的實現，我用一個TimeRange類型來存儲每個Tuple<DateTime, DateTime>，其他在這裏做。我沒有在這裏列入，只是爲了保持專注。

Answer 5

我用TIMERANGE作爲容器存儲所述範圍內：

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

    public DateTime start; 
    public DateTime end; 
} 

它把在組合兩個時間段的問題。因此，當前時間範圍（工作）與先前合併的時間範圍匹配。如果之前添加的時間範圍之一已過時，則會丟棄該時間範圍，並使用新的時間範圍（根據工作和匹配時間範圍組合）。 的情況下，我想出兩個範圍（）和[]是如下：

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