我有一个日期列表，组织如下：
(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)
实际上，这关乎秒而不是日期，但理念是相同的。
您提到日期永远不会重叠，但我认为编写代码来合并重叠的日期会更简单。第一步是定义日期范围类型：
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)。
试一下这个：
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;
});
这是一个不错的查询，它能够输出你想要的结果。
Aggregate方法(source.Take(1).ToList())的参数seed应该从排序后的源数据中获取。现在这样做对于未排序的数据会失败。 - Theodor Zouliaspublic static IEnumerable<TSource> Consolidate<TSource, TProperty>(
this IEnumerable<TSource> source,
Func<TSource, TProperty> property1Selector,
Func<TSource, TProperty> property2Selector,
Func<TSource, TSource, TSource> combine)
{
var dict1 = source.ToDictionary(property1Selector);
var dict2 = source.ToDictionary(property2Selector);
if (dict1.Keys.Count == 0) yield break;
var first = dict2.Values.First(); // Start with a random element
var last = first;
var current = first;
while (true) // Searching backward
{
dict1.Remove(property1Selector(first));
dict2.Remove(property2Selector(first));
if (dict2.TryGetValue(property1Selector(first), out current))
{
first = current; // Continue searching backward
}
else
{
while (true) // Searching forward
{
if (dict1.TryGetValue(property2Selector(last), out current))
{
last = current; // Continue searching forward
dict1.Remove(property1Selector(last));
dict2.Remove(property2Selector(last));
}
else
{
yield return combine(first, last);
break;
}
}
if (dict1.Keys.Count == 0) break;
first = dict1.Values.First(); // Continue with a random element
last = first;
}
}
}
使用示例：
var source = new List<(DateTime From, DateTime To)>()
{
(new DateTime(2019, 1, 10), new DateTime(2019, 1, 12)),
(new DateTime(2019, 3, 10), new DateTime(2019, 3, 14)),
(new DateTime(2019, 1, 12), new DateTime(2019, 1, 13)),
(new DateTime(2019, 3, 5), new DateTime(2019, 3, 10)),
};
var consolidated = source
.Consolidate(r => r.From, r => r.To, (r1, r2) => (r1.From, r2.To))
.OrderBy(r => r.From)
.ToList();
foreach (var range in consolidated)
{
Console.WriteLine($"{range.From:yyyy-MM-dd} => {range.To:yyyy-MM-dd}");
}
输出：
2019年1月10日 => 2019年1月13日
2019年3月5日 => 2019年3月14日
我的方法使用了MoreLinq和函数式风格。在我看来，这种方法易于理解。这里的大部分代码都是样本数据，逻辑只有几行（GetAsDays方法和all.Segment调用）。
实现方式：我们将日期范围转换为一系列天数的集合，将这些集合合并，并将它们拆分成单独的范围（其中下一个范围的结束和开始之间超过1天）。
void Main()
{
var baseD = new DateTime(01, 01, 01);
var from = DateTime.Today.Dump("from");
var to = from.AddDays(20).Dump("to");
var range1 = GetAsDays(from, to);
var from2 = DateTime.Today.AddDays(10).Dump("from2");
var to2 = from2.AddDays(20).Dump("to2");
var from3 = DateTime.Today.AddDays(50).Dump("from2");
var to3 = from3.AddDays(10).Dump("to2");
var range2 = GetAsDays(from2, to2);
var range3 = GetAsDays(from3, to3);
var all = range3
.Union(range1)
.Union(range2)
.OrderBy(e=>e);
var split=all.Segment((iPlus1, i, a) => (iPlus1 - i) > 1);
split.Select(s=>(baseD.AddDays(s.First()),baseD.AddDays(s.Last()))).Dump();
}
public IList<int> GetAsDays(DateTime from, DateTime to)
{
var baseD = new DateTime(01, 01, 01);
var fromSpan = from - baseD;
var toSpan = to - baseD;
var set1 = Enumerable.Range((int)fromSpan.TotalDays, (int)(toSpan - fromSpan).TotalDays);
return new List<int>(set1);
}