Пересечение диапазонов (алгоритм)

Question

В качестве примера у меня есть следующие массивы:

[100,192] 
[235,280] 
[129,267] 

Как пересекающиеся массивы мы получаем:

[129,192] 
[235,267] 

Простые упражнения для людей, но проблемы для создания алгоритма, найти вторую MultiDim массив ...

Любой язык, любые идеи ..

Если кто-то не understan d меня:

Answer 1

Это реализация питон алгоритма пересечения. Его вычислительная сложность O (n^2).

a = [[100,192],[235,280],[129,267]] 

def get_intersections(diapasons): 
    intersections = [] 
    for d in diapasons: 
     for check in diapasons: 
      if d == check: 
       continue 
      if d[0] >= check[0] and d[0] <= check[1]: 
       right = d[1] 
       if check[1] < d[1]: 
        right = check[1] 
       intersections.append([d[0], right]) 
    return intersections 

print get_intersections(a) 

Answer 2

Предполагаю, что вы хотите вывести любой диапазон, который имеет 2 или более перекрывающиеся интервалы.
Таким образом, выход для [1,5], [2,4], [3,3] будет (только) [2,4].

Основная идея заключается в использовании sweep-line algorithm.

Разделить диапазоны в начальные и конечные точки.

Сортировка пунктов.

Теперь итерация через точку с переменным счетчиком инициализируется на 0.

Если вы получаете начальную точку:

• увеличивает счетчик.
• Если значение счетчика теперь равно 2, запишите эту точку в качестве начальной точки для диапазона на выходе.

Если вы получаете конечную точку

• Уменьшить счетчик.
• Если значение счетчика равно 1, запишите эту точку в качестве конечной точки для диапазона на выходе.

Примечание:

Если старт-точка и конечная точка имеют такое же значение, вы должны обработать конечную точку первой, если счетчик 1 и старт-точка сначала, если счетчик равен 2 или больше, иначе вы получите 0-мерный диапазон или разрыв 0-го уровня между двумя диапазонами на выходе.

Это должно быть довольно просто сделать, имея набор следующую структуру:

Element 
    int startCount 
    int endCount 
    int value 

Тогда вы объедините все точки с одинаковым значением в один такой элемент, установив счетчики соответственно.

Продолжительность:

O(n log n)

Пример:

Входной сигнал:

[100, 192] 
[235, 280] 
[129, 267] 

(S для запуска, E для конца)

Points | | 100 | 129 | 192 | 235 | 267 | 280 | 
Type | | Start | Start | End | Start | End | End | 
Count | 0 | 1 | 2 | 1 | 2 | 1 | 0 | 
Output | |  | [129, | 192] | [235, | 267] |  |