간격 목록에서 간격 겹침을 검색 하시겠습니까?

간격 목록에서 간격 겹침을 검색 하시겠습니까?

---

[a, b]는 a에서 b까지의 실제 줄 간격을 나타냅니다. a <b (즉, [a, b] = a <= x <= b가되는 모든 x 집합). 또한, [a, b]와 [c, d]는 x가 [a, b]와 [c, d]에 모두 포함되도록 x를 공유하는 경우 '중첩'이라고 말하십시오.

구간 목록 ([x1, y1], [x2, y2], ...)이 주어지면 [x, y]와 겹치는 모든 구간을 찾는 가장 효율적인 방법은 무엇입니까?

분명히, 나는 각각을 시도하고 O (n)에서 얻을 수 있습니다. 하지만 어떤 영리한 방법으로 간격 목록을 정렬 할 수 있는지 궁금합니다. 이진 검색을 통해 O (log N)에서 / one / 겹치는 항목을 찾은 다음 목록의 해당 위치에서 '둘러보기'하여 찾을 수 있습니다. 모든 겹치는 간격. 그러나 그러한 전략이 작동하도록 간격을 어떻게 정렬합니까?

목록 항목 자체의 요소간에 겹치는 부분이있을 수 있으므로이를 어렵게 만듭니다.

왼쪽 끝, 오른쪽 끝, 중간으로 간격을 정렬하여 시도했지만 철저한 검색으로 이어지지 않는 것 같습니다.

도움?

---

[a, b]는 b> x 및 a <y 인 경우 [x, y]와 겹칩니다. 첫 번째 요소별로 간격을 정렬하면 로그 시간의 첫 번째 조건과 일치하는 간격이 제공됩니다. 마지막 요소별로 간격을 정렬하면 로그 시간의 두 번째 조건과 일치하는 간격이 제공됩니다. 결과 세트의 교차점을 가져옵니다.

---

완벽을 기하기 위해 나는 이러한 종류의 문제에 대한 잘 알려진 데이터 구조가 있다고 덧붙이고 싶습니다. (놀라움, 놀라움) 간격 트리 로 알려져 있습니다. 기본적으로 왼쪽 (낮은) 끝점으로 정렬 된 간격을 저장하는 증강 균형 트리 (빨간색-검정색, AVL, 사용자 선택)입니다. 증가는 각 노드가 하위 트리에 가장 큰 오른쪽 (높은) 엔드 포인트를 저장한다는 것입니다. 이 트리를 사용하면 O (log n) 시간에서 모든 겹치는 간격을 찾을 수 있습니다.

CLRS 14.3에 설명되어 있습니다.

---

'쿼드 트리'는 주로 2 개 차원으로 충돌 검출의 효율을 개선하는 데 사용되는 데이터 구조이다.

비슷한 1 차원 구조를 생각 해낼 수있을 것 같습니다. 이것은 약간의 사전 계산이 필요하지만 O (log N) 성능을 가져야합니다.

기본적으로 가능한 모든 간격을 포함하는 루트 '노드'로 시작하고 트리에 노드를 추가 할 때 중간 지점의 왼쪽 또는 오른쪽에 있는지 여부를 결정합니다. 중간 지점을 지나면 두 구간으로 나누고 (그러나 원래 부모를 기록) 거기에서 재귀 적으로 진행합니다. 메모리를 절약하고 성능을 향상시킬 수있는 트리의 깊이에 제한을 설정할 수 있지만 약간 복잡해집니다 (노드에 간격 목록을 저장해야 함).

그런 다음 간격을 확인할 때 기본적으로 삽입 될 모든 리프 노드를 찾고 해당 노드 내의 부분 간격에서 교차를 확인한 다음 '원래'부모로 기록 된 간격을보고합니다.

---

말하자면 '커프에서 벗어난'생각 만하면됩니다.

두 개의 목록으로 구성 할 수 있습니다. 하나는 간격 시작 용이고 다른 하나는 간격 종료 용입니다.

이런 식으로 y를 간격 목록 (예 : 이진 검색)의 시작 항목과 비교하여이를 기반으로 후보를 줄일 수 있습니다.

그런 다음 x를 간격 목록 끝의 항목과 비교할 수 있습니다.

편집하다

사례 : 한 번 꺼짐

일회성 상황에서 단일 간격 만 간격 목록과 비교하는 경우 이상적인 정렬이 O (n)이므로 정렬이 도움이되지 않는다고 생각합니다 .

모든 x를 통해 선형 검색을 수행하여 불가능한 간격을 잘라낸 다음 나머지 y를 통해 또 다른 선형 검색을 수행하면 전체 작업을 줄일 수 있습니다. 이것은 여전히 ​​O (n)이지만 이것이 없으면 2n 비교를 수행하는 반면 평균적으로 이런 방식으로 (3n-1) / 2 비교 만 수행합니다.

나는 이것이 정렬되지 않은 목록에 대해 할 수있는 최선이라고 생각합니다.

사례 : 사전 분류는 중요하지 않습니다.

단일 간격을이 간격 목록과 사전 정렬 한 목록과 반복적으로 비교하는 경우 더 나은 결과를 얻을 수 있습니다. 위의 프로세스는 여전히 적용되지만 첫 번째 목록에서 이진 검색을 수행하면 두 번째 목록에서 O (mn)와 반대로 O (m log n)을 얻을 수 있습니다. 여기서 m은 비교되는 단일 간격의 수입니다. 여전히 전체 비교를 줄이는 이점이 있습니다. [m (3 (log n)-1) / 2에 비해 2m log n]

---

동시에 왼쪽 끝과 오른쪽 끝을 기준으로 정렬하고 두 목록을 모두 사용하여 겹치는 값을 제거 할 수 있습니다. 목록이 왼쪽 끝으로 정렬되면 테스트 범위의 오른쪽 끝 오른쪽에있는 간격이 겹칠 수 없습니다. 목록이 오른쪽 끝으로 정렬되면 테스트 범위 왼쪽 끝의 왼쪽에있는 간격이 겹칠 수 없습니다.

예를 들어 간격이

[1,4], [3,6], [4,5], [2,8], [5,7], [1,2], [2,2.5]

그리고 겹치는 부분을 [3,4]찾은 다음 왼쪽 끝으로 정렬하고 테스트 오른쪽 끝의 위치를 ​​표시합니다 (오른쪽 끝이 값보다 커서 4범위에 포함됨).

[1,4], [1,2], [2,2.5], [2,8], [3,6], [4,5], *, [5,7]

[5,7]겹칠 수 없다는 것을 알고 , 테스트의 오른쪽 끝과 마킹 위치로 정렬

[1,2], [2,2.5], *, [1,4], [4,5], [3,6], [5,7], [2,8]

당신도 알다시피 [1,2]과 [2,2.5]겹칠 수 없습니다

두 가지 정렬과 검색을 수행해야하기 때문에 이것이 얼마나 효율적인지 확실하지 않습니다.

---

다른 답변에서 볼 수 있듯이 대부분의 알고리즘은 특수 데이터 구조와 함께 제공됩니다. 예를 들어, 정렬되지 않은 간격 목록의 경우 입력 O(n)이 가장 좋습니다. (일반적으로 알고리즘을 결정하는 데이터 구조 측면에서 생각하는 것이 더 쉽습니다).

이 경우 귀하의 질문은 완전하지 않습니다.

• 전체 목록을 받았습니까, 아니면 실제로 생성 한 사람입니까?

• 그러한 조회를 한 번만 수행해야합니까, 아니면 여러 번 수행해야합니까?

• 지원해야 할 작업과 빈도에 대한 추정치가 있습니까?

예를 들어 이러한 조회를 한 번만 수행해야하는 경우 이전에 목록을 정렬하는 것은 가치가 없습니다. 많은 경우 더 비싼 정렬 또는 "1D ​​쿼드 트리"생성이 상각됩니다.

However, it would be difficult to solve it, because a simple quadtree (as I understand it) is able just to detect the collistion, but it's not able to create the list of all the segments that are overlapping with your input.

One simple implementation would be an ordered (by coordonate) list where you insert all the segment ends with flag start/end and with segment number. In this way, by parsing it (still O(n), but I doubt you can make it faster if you also need the list of all the segments that overlaps), and keeping the track of all opened segments that were not closed at "check points".

참고URL : https://stackoverflow.com/questions/4446112/search-for-interval-overlap-in-list-of-intervals