我在处理TimeSpan对象列表时遇到了一些麻烦，但没有很多代码，这些代码似乎仍然无法涵盖所有可能发生的事情，tbh，我想我现在有点代码/逻辑盲了！
我有一个可能会发生重叠的时间跨度列表，但我需要一个没有重叠但覆盖所有时间跨度的整个持续时间的时间跨度的列表。
例如(请注意，日期为ddMMyyyy格式(：
TS1: 01/01/2020 to 01/02/2020 (1 month)
TS2: 01/03/2020 to 01/05/2020 (2 months)
TS3: 01/04/2020 to 01/07/2020 (3 months with a 1 month overlap with TS2)
TS4: 01/10/2020 to 01/12/2020 (2 months)
TS5: 01/09/2020 to 01/01/2021 (4 months with a 2 month overlap with TS4)
所以在这种情况下，我希望得到3个时间跨度：
TSA: 01/01/2020 to 01/02/2020 (1 month - same as TS1 as there are no overlaps)
TSB: 01/03/2020 to 01/07/2020 (4 months - combination of TS2 and TS3)
TSC: 01/09/2020 to 01/01/2021 (4 months - combination of TS4 and TS5, technically only TS5 as TS4 is fully encompassed by TS5)
我试过在网上研究一种算法，但没有成功。
欢迎提出任何建议。
这根本没有优化，但在语义上您可以通过添加块并查找重叠，然后合并这些重叠来实现这一点；类似于：
using System;
using System.Collections.Generic;
using System.Globalization;
static class P
{
static void Main()
{
var results = new List<(DateTime From, DateTime To)>();
Add("01/01/2020", "01/02/2020");
Add("01/03/2020", "01/05/2020");
Add("01/04/2020", "01/07/2020");
Add("01/10/2020", "01/12/2020");
Add("01/09/2020", "01/01/2021");
// SEE BELOW, IMPORTANT
results.Sort(); // initial sort
while (MergeOneOverlap()) { }
foreach (var range in results)
{
Console.WriteLine($"{range.From:dd/MM/yyyy} - {range.To:dd/MM/yyyy}");
}
bool MergeOneOverlap()
{
for (int i = 0; i < results.Count; i++)
{
var x = results[i];
for (int j = i + 1; j < results.Count; j++)
{
var y = results[j];
if (x.Intersects(y))
{
results[i] = x.Merge(y);
results.RemoveAt(j);
results.Sort(); // retain sort while making progress
return true;
}
}
}
return false;
}
void Add(string from, string to)
=> results.Add(
(DateTime.ParseExact(from, "dd/MM/yyyy", CultureInfo.InvariantCulture),
DateTime.ParseExact(to, "dd/MM/yyyy", CultureInfo.InvariantCulture)));
}
static bool ContainsInclusive(this (DateTime From, DateTime To) range, DateTime when)
=> when >= range.From && when <= range.To;
static bool Intersects(this (DateTime From, DateTime To) x, (DateTime From, DateTime To) y)
=> x.ContainsInclusive(y.From) || x.ContainsInclusive(y.To) || y.ContainsInclusive(x.From) || y.ContainsInclusive(x.To);
static (DateTime From, DateTime To) Merge(this (DateTime From, DateTime To) x, (DateTime From, DateTime To) y)
=> (x.From < y.From ? x.From : y.From, x.To > y.To ? x.To : y.To);
}
如果这是针对大量数据，你必须考虑更聪明的方法来避免O(N^3(问题。它可能有助于合并每个添加，如果这通常会减少项目数量的话。
也可以将复杂性降低到O(N^2(和纯粹向前合并(即不要在成功合并时中断(，但我还没有充分思考这一点的含义。而O(N^2(仍然相当糟糕。
对于大数据，使用排序列表可能会有所帮助，因此您可以对开始日期进行二进制搜索以找到插入点。不过，这比我想在这里写的要复杂得多。
我95%确信这也很好，即O(N^2(:
MergeOverlaps();
foreach (var range in results)
{
Console.WriteLine($"{range.From:dd/MM/yyyy} - {range.To:dd/MM/yyyy}");
}
void MergeOverlaps()
{
results.Sort();
for (int i = 0; i < results.Count; i++)
{
var x = results[i];
for (int j = i + 1; j < results.Count; j++)
{
var y = results[j];
if (x.Intersects(y))
{
results[i] = x = x.Merge(y);
results.RemoveAt(j--);
}
}
}
}
我建议尝试强力搜索或深度优先搜索算法。
首先，您按开始日期对时间跨度进行排序。
刷力：您尝试所有组合，并按重叠/不重叠进行评分，您可能希望按覆盖的总时间跨度进行评分。
DEPTH-FIRST-SEARCH:/strong>编写一个递归算法，从添加第一个区间开始，然后添加更多区间，并在出现重叠时回溯。