如何在C＃中的列表中合并日期范围

Question

我有一个这样组织的日期列表：

(From, To)
(From, To)
...
(From, To)

我正在尝试找到如何以有效方式合并范围（它必须相当快，因为​​它是实时合并财务数据流）。

日期不能重叠。

我在想的是：

按时间对所有内容进行排序，然后遍历对以查看Pair1.To == Pair2.From是否合并它们，但这意味着要进行多次迭代。

有没有更好的方法可以做到这一点，例如单次通过

这里有些例子

(2019-1-10, 2019-1-12)
(2019-3-10, 2019-3-14)
(2019-1-12, 2019-1-13)

预期输出：

(2019-1-10, 2019-1-12) + (2019-1-12, 2019-1-13) -> (2019-1-10, 2019-1-13)
(2019-3-10, 2019-3-14) -> (2019-3-10, 2019-3-14)

实际上，这实际上是大约几秒钟，而不是日期，但是想法是相同的。

Answer 1

您提到日期永远不会重叠，但是我认为编写仅合并重叠日期的代码稍微简单一些。第一步是定义日期范围类型：

class Interval
{
    public DateTime From { get; set; }
    public DateTime To { get; set; }
}

然后，您可以定义一个扩展方法来检查两个间隔是否重叠：

static class IntervalExtensions
{
    public static bool Overlaps(this Interval interval1, Interval interval2)
        => interval1.From <= interval2.From
           ? interval1.To >= interval2.From : interval2.To >= interval1.From;
}

请注意，此代码假定这样From <= To做，因此您可能想要更改Interval为不可变类型并在构造函数中进行验证。

您还需要一种合并两个间隔的方法：

public static Interval MergeWith(this Interval interval1, Interval interval2)
    => new Interval
    {
        From = new DateTime(Math.Min(interval1.From.Ticks, interval2.To.Ticks)),
        To = new DateTime(Math.Max(interval1.From.Ticks, interval2.To.Ticks))
    };

下一步是定义另一种扩展方法，该方法迭代间隔序列并尝试合并连续的重叠间隔。最好使用迭代器块完成此操作：

public static IEnumerable<Interval> MergeOverlapping(this IEnumerable<Interval> source)
{
    using (var enumerator = source.GetEnumerator())
    {
        if (!enumerator.MoveNext())
            yield break;
        var previousInterval = enumerator.Current;
        while (enumerator.MoveNext())
        {
            var nextInterval = enumerator.Current;
            if (!previousInterval.Overlaps(nextInterval))
            {
                yield return previousInterval;
                previousInterval = nextInterval;
            }
            else
            {
                previousInterval = previousInterval.MergeWith(nextInterval);
            }
        }
        yield return previousInterval;
    }
}

如果两个连续的时间间隔不重叠，则会产生前一个时间间隔。但是，如果它们重叠，则通过合并两个间隔来更新前一个间隔，并将合并的间隔保留为下一次迭代的前一个间隔。

您的样本数据未排序，因此在合并间隔之前必须对它们进行排序：

var mergedIntervals = intervals.OrderBy(interval => interval.From).MergeOverlapping();

但是，如果对实际数据进行了排序（如注释中所示），则可以跳过排序。该算法将对数据进行一次传递，因此为O(n)。

Answer 2

试一试：

var source = new[]
{
    new { from = new DateTime(2019, 1, 10), to = new DateTime(2019, 1, 12) },
    new { from = new DateTime(2019, 3, 10), to = new DateTime(2019, 3, 14) },
    new { from = new DateTime(2019, 1, 12), to = new DateTime(2019, 1, 13) },
};

var data =
    source
        .OrderBy(x => x.from)
        .ThenBy(x => x.to)
        .ToArray();

var results =
    data
        .Skip(1)
        .Aggregate(
            data.Take(1).ToList(),
            (a, x) =>
            {
                if (a.Last().to >= x.from)
                {
                    a[a.Count - 1] = new { from = a.Last().from, to = x.to };
                }
                else
                {
                    a.Add(x);
                }
                return a;
            });

这是一个很好的查询，它给出了您想要的输出。