Hợp nhất các khoảng thời gian chồng chéo?

Question

tôi có như sau:

public class Interval 
{ 
    DateTime Start; 
    DateTime End; 
} 

Tôi có một đối tượng List<Interval> chứa nhiều khoảng thời gian. Tôi cố gắng để đạt được những điều sau đây (tôi đã sử dụng số để làm cho nó dễ hiểu):

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

Tôi hiện làm điều này bằng Python như sau:

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) 

nhưng đang cố gắng để đạt được như vậy trong C# (LINQ sẽ là tốt nhất nhưng tùy chọn). Bất kỳ đề xuất về cách làm điều này một cách hiệu quả?

Answer 1

Điều này có thể không phải là giải pháp đẹp nhất, nhưng nó có thể làm việc tốt

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

Bất kỳ thông tin phản hồi sẽ được đánh giá cao.

Kính trọng

Answer 2

Loại hợp nhất này thường được coi là gấp bằng ngôn ngữ chức năng. Tương đương LINQ là 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; 
} 

tôi làm lớp Interval generic (Interval<T> where T : IComparable<T>), thêm một phương pháp bool Contains(T value), và làm cho nó bất biến, nhưng bạn không nên cần phải thay đổi nó nhiều nếu bạn muốn sử dụng định nghĩa lớp như bạn có nó ngay bây giờ.

Answer 3

Đây là phiên bản sử dụng yield return - Tôi thấy dễ đọc hơn là thực hiện truy vấn Aggregate, mặc dù nó vẫn được đánh giá lười biếng. Điều này giả định bạn đã ra lệnh cho danh sách đã có, nếu không, chỉ cần thêm bước đó.

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

Tôi bị bao vây bởi hội chứng "Không được tạo ở đây" tối nay, vì vậy đây là của tôi. Sử dụng một điều tra viên trực tiếp đã lưu cho tôi một vài dòng mã, làm cho nó rõ ràng hơn (IMO), và xử lý các trường hợp không có hồ sơ. Tôi cho rằng nó có thể chạy một smidge nhanh hơn cũng như nếu bạn quan tâm về điều đó ...

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

Thực hiện của riêng tôi, tôi sử dụng một loại TimeRange để lưu trữ mỗi Tuple<DateTime, DateTime>, như khác ở đây làm gì. Tôi không bao gồm ở đây chỉ đơn giản là để tập trung/về chủ đề.

Answer 5

tôi đã sử dụng TimeRange như một container lưu trữ các dãy:

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

    public DateTime start; 
    public DateTime end; 
} 

Nó chia vấn đề trong việc kết hợp hai dao động thời gian. Do đó, phạm vi thời gian hiện tại (công việc) được đối sánh với phạm vi thời gian được hợp nhất trước đó. Nếu một trong các phạm vi thời gian đã thêm trước đó là lỗi thời, nó sẽ bị loại bỏ và phạm vi thời gian mới (được kết hợp từ công việc và phạm vi thời gian phù hợp) được sử dụng. Các trường hợp tôi đã tìm ra cho hai phạm vi() và [] như sau:

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