从 TimeSpans 列表中查找不同的 TimeSpan 持续时间

Question

我在没有大量代码的情况下尝试处理 TimeSpan 对象列表时遇到了一些麻烦，这些代码似乎仍然没有涵盖所有可能发生的情况，老实说，我想我已经走了一点 code/logic 现在瞎了！

我有一个可能会发生重叠的 TimeSpans 列表，但我需要一个没有重叠但涵盖所有 TimeSpans 的整个持续时间的 TimeSpans 列表。

例如（请注意，日期采用 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)

我试过在线研究算法，但没有成功。

非常欢迎任何建议。

Answer 1

我建议尝试暴力搜索或 depth-first 搜索算法。

首先按开始日期对时间跨度进行排序。

蛮力： 您尝试所有组合并按 overlap/not 重叠对它们进行评分，并且您可能希望按覆盖总时间跨度的多少对它们进行评分。

DEPTH-FIRST-SEARCH: 编写一个递归算法，首先添加第一个间隔，然后在发生重叠时添加更多间隔和回溯。

Answer 2

这根本没有优化，但是在语义上您可以通过添加块并寻找重叠部分，然后合并这些重叠部分来做到这一点；类似于：

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

从 TimeSpans 列表中查找不同的 TimeSpan 持续时间

Find distinct TimeSpan duration from a list of TimeSpans

c#

timespan