Объединение и разность отрезков

public Class Line
{
    public int Type;
    public float From;
    public float To;
}

Трансформируем данные в (значение-дельта). Значение - это число из колонки "от" или "до" (всё валим в кучу, короче), а дельта - для начала типа 2 это +1, для конца типа 2 это -1, для начала типа 3 это -N, где N больше количества записей типа 2, для конца типа 3 соответственно +N. Полученную кучу сортируем по Значению, считаем нарастающую сумму по Дельте. Если сумма стала больше нуля - начинаем интервал, если ноль или меньше - заканчиваем.

Всё.

Применительно к показанным исходным данным это получится

Значение Дельта Сумма
0         1      1
3        -5     -4
5         1     -3
7        -1     -4
9        -1     -5
10        1     -4
11        5      1
12       -1      0
15        1      1
17       -1      0

Соответственно интервалы 0-3, 11-12 и 15-17.

Если порядок важен, то обрабатываем последовательно - сперва две записи, затем итог (ему присваивается тип 2) плюс третья, итог плюс четвёртая... для исходных данных это будет:

Первые две:

0   1   1
5   1   2
7   -1  1
9   -1  0

Итого - (0-9).

Итог плюс третья:

0   1   1
9   -1  0
10  1   1
12  -1  0

Итого - (0-9), (10-12).

Итог плюс четвёртая:

0   1   1
3   -5  -4
9   -1  -5
10  1   -4
11  5   1
12  -1  0

Итого - (0-3), (11-12)

Добавляем пятую:

0   1   1
3   -1  0
11  1   1
12  -1  0
15  1   1
17  -1  0

Результат - (0-3), (11-12), (15-17)

Способ, предложенный @Akina оптимален и решает задачу, но т.к. количество значений относительно небольшое предлагаю как альтернативу подход «в лоб», который возможно будет легче читать/тестировать.

Подготовка:

Для подготовки нужно создать вспомогательные методы в Line:

• метод, проверяющий пересечение отрезков, вроде bool DoesIntrsect(Line other)
• метод, объединяющий два пересекающихся отрезка: Line Join(Line other)
• метод, отнимающий один отрезок от другого: List<Line> Subtract(Line other)

Первые два достаточно тривиальны. Для третьего нужно будет рассмотреть несколько случаев:

    Случай 1   │   Случай 2  │  Случай 3   │  Случай 4    │  Случай 5 
 ----          │   -----     │      -----  │ -----------  │     ----
        ————   │      ————   │   —————     │    ——————    │   —————————

В первых трех случаях возвращается один отрезок, в четвертом — два, в пятом — ни одного.

Алгоритм:

Основная идея: создать список отрезков, который на каждом шаге содержит текущий результат и для которого выполняются условия:

• не содержит пересекающихся отрезков;
• отсортирован.

Сначала список пустой. Пошагово обрабатываем отрезки. Для каждого шага:

• удаляем из списка все отрезки, пересекающиеся с текущим;
• если текущий отрезок вычитается: от каждого удаленного отрезка отнимаем текущий, результат Subtract добавляем в список;
• если текущий отрезок объединяется: все удаленные отрезки по очереди объединяем с текущим, результат объединения добавляем в список.

То, что список отсортирован потенциально позволит сократить пробег по списку. Возможно, на текущих объемах это и не требуется.

NB: Рассмотрите особенно внимательно к случаям, когда отрезки касаются (они должны объединяться)/совпадают (результат вычитания должен быть пустым). В крайних точках легко допустить ошибку.