合并重叠的时间间隔？

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

这是一个使用的版本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 2

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

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

任何反馈将不胜感激。

问候