Как написать метод, который находит все пересечения в массиве диапазонов?

У меня есть массив, подобный этому

[
 [0, 10]**,
 [1, 3]**,
 [5, 11]**,
 [14, 20]**,
 [10, 11]**
]

** Обозначает объект, содержащий начальный и конечный индексы, показанные в массиве

Теперь перекрестков [1, 3], [5,10], [10,11]

Как лучше всего написать метод, который возвращает объекты, содержащие пересекающиеся наборы? (Можно просто хранить их в массиве конфликтующих вещей по ходу дела)

Самая большая проблема, с которой я сталкиваюсь, заключается в том, как мне сделать так, чтобы каждый объект сравнивался с каждым другим объектом?

нет! способы сделать это (думаю, я немного заржавел в своей комбинаторике)


arrays set algorithm intervals intersection
person NullVoxPopuli    schedule 31.10.2011    source источник
comment
начальные и конечные индексы текстовых блоков из больших фрагментов текста.   -  person NullVoxPopuli    schedule 01.11.2011
comment
Не могли бы вы объяснить, как вы переходите от исходных данных к пересечениям и конфликтующим множествам? Это вообще непонятно.   -  person Matt Fenwick    schedule 01.11.2011
comment
Что вы пробовали? Я так понимаю, вы хотите, чтобы пересекающиеся пары были (0, 1), (0, 2), (0, 4), (2, 4).   -  person Jim Mischel    schedule 01.11.2011
comment
@MattFenwick, я не думаю, что то, как я получаю данные, не важно.   -  person NullVoxPopuli    schedule 01.11.2011
comment
@JimMischel Я застрял в сравнении каждого объекта с любой другой частью объекта. Я думаю, что мне может понадобиться сделать что-то рекурсивное. знак равно   -  person NullVoxPopuli    schedule 01.11.2011
comment
Я тоже, просто пытаюсь понять проблему.   -  person Matt Fenwick    schedule 01.11.2011
comment
Вы можете изучить деревья интервалов: dgp.toronto.edu/~jstewart/378notes/ 22 интервала. Вы можете создать его в O(n log n) и запросить n элементов в n log n. Хотя, возможно, вы сможете пройти его в O(n).   -  person Jim Mischel    schedule 01.11.2011
comment
Для сравнения каждого объекта с любым другим используется простой вложенный цикл. Посмотрите на сортировку выбором. Это будет хорошо работать, если количество диапазонов относительно невелико.   -  person Jim Mischel    schedule 01.11.2011
comment
Это может быть полезно stackoverflow.com/questions/7438404/ (особенно второй ответ)   -  person hatchet - done with SOverflow    schedule 01.11.2011

Ответы (1)


arrow_upward
0
arrow_downward

Отсортируйте интервалы по времени начала (или вместо этого отсортируйте массив индексов по времени начала, чтобы не потерять индексы).

После этого вы можете сделать один проход, обнаружив все пересечения/конфликты.

Range array[N];

sort(array);
int i=0;
while(i<N){
    Range curr = array[i];  //invariant: curr doesn't intersect with anyone befor it
    i++;
    while(i < N && array[i].start <= curr.end){
        output that curr and array[i] intersect;
        if(array[i].end > curr.end){
            curr = array[i]
        }
        i++;
    }
}
person hugomg    schedule 31.10.2011
comment
Если я не ошибаюсь, это метод сортировки выбором, верно? Сравните каждый диапазон со всеми диапазонами ниже него, с ранним временем начала тестирования и curr_end. - person Jim Mischel; 01.11.2011
comment
Я не совсем понимаю это, не могли бы вы объяснить немного лучше? вы используете стек. =\ О, и я должен сказать, что индексы так же важны, поскольку на самом деле это массив объектов, у которых есть начальный и конечный индексы. Я обновлю свой вопрос, поскольку он актуален. - person NullVoxPopuli; 01.11.2011
comment
эм.. не совсем. вы должны также сохранить самые большие .end, иначе вы можете пропустить пересечения. - person Karoly Horvath; 01.11.2011
comment
@yi_H: да, кажется, я исправил это сейчас - person hugomg; 01.11.2011
comment
это самый эффективный способ сделать это? я имею в виду, это выглядит как O(n^n) - person NullVoxPopuli; 01.11.2011
comment
Мне это кажется O(n). Вы начинаете с i=0, и я доходит до N один за другим. (обратите внимание, что каждый элемент массива обрабатывается только один раз) - person hugomg; 01.11.2011