Необходимо написать на .Net структуру данных “Дерево интервалов” основанную на красно-черном дереве. Алгоритм не очень сложный, нужно просто иметь представление о красно-черных деревьях.

Детали задания:

Что такое интервал?

Интервал представляет собой пару чисел: начало и конец. Концы интервала могут быть закрытыми и открытыми.

Класс определяющий интервал: /извините, парсер съедает форматирование, не знаю, как поправить/

public class Interval<T> where T : IComparable<T>
{
public Interval(T left, T right, bool isLeftIncluded, bool isRightIncluded)
{
Left = left;
Right = right;
IsLeftIncluded = isLeftIncluded;
IsRightIncluded = isRightIncluded;
}

public T Left { get; private set; }
public T Right { get; private set; }
public bool IsLeftIncluded { get; private set; }
public bool IsRightIncluded { get; private set; }
}

Что такое дерево интервалов?
Дерево интервалов - это структура данных оптимизированная для работы с интервальными данными.
Основные характеристики:
- Вставка и удаление интервала за Lg(n)
- Поиск интервала на заданном отрезке за Lg(n)
- Поиск пустых мест (дыр) на отрезке

Интерфейс, определяющий интервальное дерево:

public interface IIntervalTree<T, I>
where T: IComparable<T>
where I: Interval<T>
{
void Add(I interval);
void Clear();
int Count { get; }
bool Remove(I interval);
I FindOverlap(T point);
IEnumerable<I> FindOverlaps(Interval<T> interval);
IEnumerable<I> Gaps();
IEnumerable<I> Gaps(Interval<T> interval);
IEnumerable<I> EnumerateForward(I point);
IEnumerable<I> EnumerateBackward(I point);
}

Что почитать про дерево интервалов:
- Кормен, “ Алгоритмы построение и анализ”, окончание главы о бинарных деревьях. Тут есть базовое описание алгоритма.
- Вики (только англ): https://en.wikipedia.org/wiki/Interval_tree
- https://www.youtube.com/watch?v=dQF0zyaym8A

Что хотелось бы услышать от исполнителя:
- Описание опыта связанного с алгоритмами/структурами данными. Проекты в универе.
- Мысли по поводу реализации. Предполагаемые сложные места, предполагаемые пути их решения.
- Сколько предполагаемо займет реализация?
- Когда можно начать?
- Цена?