如何在无序的日期时间范围集中找到非重叠日期时间范围的最长(按时间顺序)序列?

不久前我做了一个编程测试,我对这个问题感到困惑:找出最长的(基本上是考虑总和或不重叠的活动,活动定义如下:

public class Activity
{
    public string Name { get; }
    public DateTime Start { get; }
    public DateTime Stop { get; }
    public TimeSpan Duration => Stop - Start;

    private Activity(string name, DateTime start, DateTime stop)
    {
        if (start > stop)
        {
            throw new ArgumentOutOfRangeException(nameof(start));
        }

        Name = name ?? throw new ArgumentNullException(nameof(name));
        Start = start;
        Stop = stop;
    }
}

public class LongestNonOverlappingActivitySequenceFinder
{
    public IEnumerable<Activity> Find(IEnumerable<Activity> activities)
    {
        // Logic goes here...
    }
}

public class Program
{
    public static void Main(params string[] args)
    {
        var reference = DateTime.Today.AddHours(0);
        var activites = new[]
        {
            new Activity("A", reference, reference.AddHours(1)),
            new Activity("B", reference.AddHours(1), reference.AddHours(2)),
            new Activity("C", reference.AddHours(1), reference.AddHours(1.5)),
            new Activity("D", reference.AddHours(2), reference.AddHours(3)),
        };

        foreach (var activity in LongestNonOverlappingActivitySequenceFinder.FindLongestNonOverlappingRangeSet(activites))
        {
            Console.WriteLine(activity.Name);
        }
    }
}

我在中使用的解决方案类似于此处的建议: How do I get all non-overlapping permutations for a series of time blocks?

但它是递归的+非常贪婪的,基本上这是我的测试解决方案,但它保持超时。

• 只要所有活动的累计持续时间最长且不重叠,就可以支持两个活动之间的差距