2

У меня есть список объектов-отрезков следующего вида:

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

Поле type может быть 2 или 3, если 2, то нужно объединить отрезки, если 3 то из всех предыдущих отрезков вычесть текущий.
Например, пусть список с такими элементами:
введите сюда описание изображения

Порядок элементов в списке важен.

В результирующем списке мне необходимо получить следующий список:

введите сюда описание изображения

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

за сплошной вертикальной чертой, я формирую итоговый вариант

Подкиньте идею, для решения данной задачи. Любая помощь приветствуется.

5
  • Может стоит уточнить ограничения (сколько будет отрезков, сколько времени выделено на обработку списка)? 15 июн 2017 в 12:07
  • @defaultlocale, в списке может быть как один элемент, так и 20. Думаю, случаи с элементами более 20 невероятны. С таким максимальным количеством элементов, алгоритм должен работать моментально.
    – Naf
    15 июн 2017 в 12:11
  • ru.stackoverflow.com/questions/671814/… это не оно случайно?
    – pavel
    15 июн 2017 в 12:41
  • @pavel, что-то похожее, с одной лишь разницей, что там нет условия, когда какой-то человек стирает краску с веревки.
    – Naf
    15 июн 2017 в 12:45
  • @Naf просто удаление эквивалентно добавлению [0,a) и (b, inf) поэтому по факту код работать будет.
    – pavel
    15 июн 2017 в 13:09

2 ответа 2

4

Трансформируем данные в (значение-дельта). Значение - это число из колонки "от" или "до" (всё валим в кучу, короче), а дельта - для начала типа 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)

5
  • Отличное решение для случая, когда последовательность роли не играет. Из условия неясно: если отрезок 3-11 будет идти первым будет ли он вычитаться из последующих. 15 июн 2017 в 12:12
  • @defaultlocale, порядок важен. если встречается элемент с типом 3, то нужно произвести вычитание из всех предшествующих его элементов. Если отрезок 3-11 будет идти первым, то он вообще никакой роли для результирующей последовательности не будет играть.
    – Naf
    15 июн 2017 в 12:18
  • порядок важен Вот это - подробно, крупными буквами в описание вопроса.
    – Akina
    15 июн 2017 в 12:20
  • И если порядок важен - то алгоритм придётся дополнить колонкой видимости (ну или экранирования, один хрен), и в нарастающем итоге это экранирование учитывать. Но проще будет обрабатывать последовательно вот именно как это делается графически. Там вариантов-то действий всего 4 - добавить отрезок, слить два/три отрезка, усечь/рассечь отрезок, удалить отрезок. А поскольку отрезки хранить надо в сортированном порядке, это будет элементарно.
    – Akina
    15 июн 2017 в 12:26
  • Ну либо можно трансформировать в такое - вышеописанным алгоритмом обрабатываем первые две записи, к итогу добавляем третью запись и обрабатываем, к итогу добавляем четвёртую... и так пока не кончатся.
    – Akina
    15 июн 2017 в 12:27
1

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

Подготовка:

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

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

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

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

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

Алгоритм:

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

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

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

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

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

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.