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

Question

我有这样安排的日期清单：

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

我试图找出如何有效地合并范围(它必须相当快，因为它是实时合并金融数据流)。

日期不重叠。

我在想的是：

按时间对所有内容进行排序，然后遍历成对以查看是否对== pairs 2。从合并它们，但这意味着几次迭代。

有没有更好的方法来做到这一点，就像一次传球

以下是一些例子

(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.From.Ticks)),
        To = new DateTime(Math.Max(interval1.To.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;
            });

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

Answer 3

创建两个字典(即散列映射)，一个使用To date作为键，From-To date作为值，另一个以From date作为键。

迭代您的日期范围，并为每个范围检查从日期是否存在作为键在“日期键”字典中，反之亦然。

如果两者都不匹配，那么将范围添加到两个字典中。

如果其中一个中有匹配，而另一个没有匹配，则从两个字典中删除匹配范围(使用适当的键)，将新范围与现有范围合并，并将结果添加到这两个字典中。

如果两个字典中都有匹配(所添加的范围填补了一个漏洞)，那么从两个字典中删除两个匹配，合并这三个范围(两个现有的和一个新的)，并将结果添加到两个字典中。

最后，您的字典包含一组未排序的所有日期范围，您可以通过迭代其中一个字典的键来提取这些日期范围。