Как найти самую длинную (по времени) последовательность непересекающихся диапазонов DateTime в неупорядоченном наборе диапазонов DateTime? - PullRequest
Новая
       10

Как найти самую длинную (по времени) последовательность непересекающихся диапазонов DateTime в неупорядоченном наборе диапазонов DateTime?

0 голосов
/ 28 октября 2018

У меня был тест на программирование не так давно, и я озадачился этой проблемой: выяснить самое продолжительное (в основном с учетом суммы или непересекающихся действий, с действиями, определенными как: 

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

Решение, которое я использовал во время, похоже на то, что предлагается здесь: Как получить все непересекающиеся перестановки для ряда временных блоков?

Но это рекурсивно + довольно жадно, в основном это было мое решение для теста, но оно держало тайм-аут.

Примечания перед сном:

  • Может поддерживать разрыв между двумя действиями, если совокупная продолжительность всех действий является самой длинной и без наложения

  • Если существует одна длинная операция, продолжительность которой равна сумме длительностей непересекающихся операций, то мы подбираем этот набор непересекающихся операций (идея состоит в том, чтобы запланировать как можно больше действий) .

...