Мотивация

В рамках задачи, связанной с "горизонтами планирования", я работал с интервалами времени. И через небольшой такой интервал случилась знакомая многим история - разбросанная тут и там логика стала унифицироваться, и эту унификацию захотелось оформить в отдельный компонент.

.NET включает относительно хорошую систему типов для работы с датами и временем https://learn.microsoft.com/en-us/dotnet/standard/datetime/. Когда не хватает стандартных типов, можно использовать NodaTime. Но ни BCL, ни Noda не содержат решения для работы c интервалами времени (точнее для анализа множества интервалов). Возможно, потому что это элементарная структура данных. А возможно, потому что она нужна для очень узкого круга задач. "Можно, а зачем?" (с)

Решение

В общем, вижу цель, не вижу препятствий. И очередной велосипед был изобретен, почищен, поглажен и красиво выложен на GitHub.

https://github.com/resnyanskiy/DateTimeRange

Само по себе представление интервала времени конечно не интересно. Это элементарная структура из двух числовых полей - начало и окончание. Интересны операции с этими интервалами. Еще интереснее операции с множествами этих интервалов, реализации которых и посвящена моя библиотека.

Сейчас реализовано три метода - Merge, Slice, Intersections. Сам код и открытый интерфейс не сложные, расписывать документацию и сценарии использования нет смысла. В репозитории есть пример (картинка выше как раз результат работы этого приложения). Можно изменить NUMBER_OF_SENSORS на какое-нибудь большое значение - но думаю картинка станет слишком "пёстрой".

Самым интересным является метод Intersections, который находит все пересечения всех интервалов (строка Max на картинке). Причем делает это в среднем за время O(n log n) или даже быстрее, при O(1) по памяти. Не менее интересным является набор тестов этого метода. На мой взгляд, их можно использовать отдельно от библиотеки, для оценки других реализаций поиска пересечений.

var lastIntersection = new DateTimeRange(); // Begin = End = DateTime.MinValue;
for (var baseIndex = 0; baseIndex < rangesArray.Length - 1; baseIndex++)
{
    var baseRange = rangesArray[baseIndex];
    if (baseRange.End <= lastIntersection.End)
        continue;
    
    var maxBegin = baseRange.Begin;
    var minEnd = baseRange.End;
    var hasIntersection = false;
    
    // at this point the `rangesArray` contains at least 2 elements
    for (var currentIndex = baseIndex + 1; currentIndex < rangesArray.Length; currentIndex++)
    {
        var currentRange = rangesArray[currentIndex];

        // no intersection, go to next `base range`
        if (baseRange.End < currentRange.Begin)
            break;

        // skip `current range` if it should not be used 
        if (currentRange.End < maxBegin)
            continue;

        // start new `intersections segment`
        if (minEnd < currentRange.Begin)
        {
            if (lastIntersection.End < maxBegin)
            {
                yield return (lastIntersection = new DateTimeRange { Begin = maxBegin, End = minEnd });
            }

            currentIndex = baseIndex;
            maxBegin = currentRange.Begin;
            minEnd = baseRange.End;
            continue; //currentIndex will be baseIndex + 1
        }

        hasIntersection = true;
        maxBegin = Max(maxBegin, currentRange.Begin);
        minEnd = Min(minEnd, currentRange.End);
    }

    if (!hasIntersection || maxBegin <= lastIntersection.End) 
        continue;
    
    yield return (lastIntersection = new DateTimeRange { Begin = maxBegin, End = minEnd });
}

Также я добавил фабричный метод, позволяющий создать набор интервалов на основе значений и порога.

IEnumerable<DateTimeRange> Create<T>(
  IEnumerable<KeyValuePair<DateTime, T>> values,
  T threshold)
  where T : IComparable<T>

Можно, например, уменьшить архив "здоровья" сервиса - из десятков heatbeat'ов за месяц получить и сохранить допустим два интервала/четыре числа.

/*
 * input:    +   + - - + + -
 * output:   |-----|   |---|
 */

var begin = DateTime.Today;
var pulse = new Dictionary<DateTime, bool>
{
    [begin.AddMinutes(1)] = true,
    //[begin.AddMinutes(2)] = true,
    [begin.AddMinutes(3)] = true,
    [begin.AddMinutes(4)] = false,
    [begin.AddMinutes(5)] = false,
    //
    [begin.AddMinutes(6)] = true,
    [begin.AddMinutes(7)] = true,
    [begin.AddMinutes(8)] = false
};

var ranges = DateTimeRange.Create(pulse, false).ToArray();

Терминология

Любопытным является вопрос наименования. В .NET есть TimeSpan, а теперь Span и Range. В NodaTime в именах типов используется Interval. Есть также слово Segment. В общем, занятный аспект английского (и в общем-то русского) технического языка.

Range или диапазон, является наиболее корректным вариантом, потому что обозначает диапазон возрастающих значений и как правило включает границы.

• Interval (интервал) более общий термин, позволяющий уточнить "открытый" он или "закрытый" и т.п.

• Segment (отрезок) используется для обозначения части чего-либо. Формально `time rage is a segment of the timeline`.

• Span (протяженность) во-первых уже используется в обозначении других типов. Во-вторых, семантически обозначает именно протяженность одним числом, в том числе отрицательную (<see cref=TimeSpan.Negate />).