C# Сортировка перечисления по периоду дат

241

28 октября 2018, 18:10

Есть свойство типа IEnumerable в которое возвращает коллекцию типа Tuple. Пример:

public IEnumerable Items {
        get { return new Tuple<DateTime, DateTime>[] {
            new Tuple<DateTime, DateTime>(DateTime.Now, DateTime.Now.AddDays(1)),
            new Tuple<DateTime, DateTime>(DateTime.Now.AddDays(1), DateTime.Now.AddDays(2)),
            new Tuple<DateTime, DateTime>(DateTime.Now.AddDays(2), DateTime.Now.AddDays(3))
        }; }
    }

Собственно вопрос в том как получить коллекцию отсортированную по диапазону дат, т.е. элементы идут последовательно в случае если дата конца периода меньше даты начала периода следующего элемента. Пример: сейчас

{12.08.2018-13.08.2018},{13.08.2018-14.08.2018},{14.08.2018-15.08.2018}

требуется

{12.08.2018-13.08.2018},{14.08.2018-15.08.2018},{13.08.2018-14.08.2018}

если рассмотреть перечисление как карту временных линий:

--{12.08.2018-13.08.2018}--------------------------
--------------{13.08.2018-14.08.2018}--------------
--------------------------{14.08.2018-15.08.2018}--

сразу видно что периоды пересекаются с другими периодами, а требуется

--{12.08.2018-13.08.2018}--------------------------
--------------------------{14.08.2018-15.08.2018}--
--------------{13.08.2018-14.08.2018}--------------

либо представить уже в двух временных линиях

--{12.08.2018-13.08.2018}-{14.08.2018-15.08.2018}--
--------------{13.08.2018-14.08.2018}--------------

Answer 1

Попробую поделить интервалы так, чтобы рядом не находилось минимум пересекающихся. Не претендую на оптимальность по времени\памяти, не заморачивался с этим.
Код сортировки:

IEnumerable<Tuple<DateTime, DateTime>> Sort(IEnumerable<Tuple<DateTime, DateTime>> intervals)
{
    var sortedByStart = intervals.OrderBy(x => x.Item1);
    var result = new List<Tuple<DateTime, DateTime>>();
    var awaitingStack = new Stack<Tuple<DateTime, DateTime>>();
    foreach (var i in sortedByStart)
    {
        if (result.Count == 0)
        {
            result.Add(i);
            continue;
        }
        if (awaitingStack.Count > 0)
        {
            while (!Intersects(awaitingStack.Peek(), result.Last()))
            {
                result.Add(awaitingStack.Pop());
            }
        }
        if (Intersects(i, result.Last()))
            awaitingStack.Push(i);
        else result.Add(i);
    }
    if (awaitingStack.Count > 0)
        result.AddRange(Sort(awaitingStack));
    return result;
}
private bool Intersects(Tuple<DateTime, DateTime> i1, Tuple<DateTime, DateTime> i2)
{
    if (i1.Item1 > i2.Item2) return false;
    if (i1.Item2 < i2.Item1) return false;
    return true;
}

Примеры использования

var today = DateTime.Today;
var intervals = new Tuple<DateTime, DateTime>[] {
        new Tuple<DateTime, DateTime>(today, today.AddDays(1)),
        new Tuple<DateTime, DateTime>(today.AddDays(1), today.AddDays(2)),
        new Tuple<DateTime, DateTime>(today.AddDays(2), today.AddDays(3))};
foreach (var i in Sort(intervals)) Console.WriteLine($"{{{i.Item1} - {i.Item2}}}");
Console.WriteLine("--------------");
intervals = new Tuple<DateTime, DateTime>[] {
        new Tuple<DateTime, DateTime>(today, today.AddDays(3)),
        new Tuple<DateTime, DateTime>(today.AddDays(1), today.AddDays(4)),
        new Tuple<DateTime, DateTime>(today.AddDays(2), today.AddDays(5))};
foreach (var i in Sort(intervals)) Console.WriteLine($"{{{i.Item1} - {i.Item2}}}");
Console.WriteLine("--------------");
intervals = new Tuple<DateTime, DateTime>[] {
        new Tuple<DateTime, DateTime>(today, today.AddDays(3)),
        new Tuple<DateTime, DateTime>(today.AddDays(1), today.AddDays(4)),
        new Tuple<DateTime, DateTime>(today.AddDays(4), today.AddDays(5))};
foreach (var i in Sort(intervals)) Console.WriteLine($"{{{i.Item1} - {i.Item2}}}");

Вывод в консоль:

{12.08.2018 0:00:00 - 13.08.2018 0:00:00}
{14.08.2018 0:00:00 - 15.08.2018 0:00:00}
{13.08.2018 0:00:00 - 14.08.2018 0:00:00}
--------------
{12.08.2018 0:00:00 - 15.08.2018 0:00:00}
{13.08.2018 0:00:00 - 16.08.2018 0:00:00}
{14.08.2018 0:00:00 - 17.08.2018 0:00:00}
--------------
{12.08.2018 0:00:00 - 15.08.2018 0:00:00}
{16.08.2018 0:00:00 - 17.08.2018 0:00:00}
{13.08.2018 0:00:00 - 16.08.2018 0:00:00}