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

Question

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

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

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

Теперь пересечения [1, 3], [5,10], [10,11]

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

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

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

Answer 1

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

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

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++;
    }
}