合并重叠的时间间隔？

我有以下内容：

public class Interval { DateTime Start; DateTime End; } 

我有一个包含多个间隔的List对象。 我试图实现以下（我使用数字使其易于理解）：

 [(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

这是一个使用yield return的版本 – 我发现它比执行Aggregate查询更容易阅读，尽管它仍然是懒惰的评估。 这假设您已经订购了列表，如果没有，只需添加该步骤。

 IEnumerable MergeOverlappingIntervals(IEnumerable 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

这可能不是最漂亮的解决方案，但也可能有效

 public static List Merge(List intervals) { var mergedIntervals = new List(); var orderedIntervals = intervals.OrderBy(x => x.Start).ToList(); 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; } 

任何反馈将不胜感激。

问候

Answer 3

今晚我被“Not Created Here”综合症所困扰，所以这是我的。 使用枚举器直接为我保存了几行代码，使其更清晰（IMO），并处理没有记录的情况。 我想如果你关心它，它可能会更快地运行…

 public IEnumerable> Merge(IEnumerable> 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 ，就像其他人一样。 我没有在这里仅仅是为了保持专注/主题。

Answer 4

这种合并通常被认为是function语言的一种折叠。 LINQ等价物是Aggregate 。

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

我将Interval类设为通用（ Interval where T : IComparable ），添加了bool Contains(T value)方法，并使其成为不可变的，但如果你想使用它，你不应该更改它你现在拥有它的类定义。

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 Merge(IEnumerable timeRanges) { List mergedData = new List(); 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; }