간격의 조합

Question

간격을 나타내는 클래스가 있습니다. 이 클래스에는 비교 가능한 유형의 두 가지 속성 "start"및 "end"가 있습니다. 이제는 그러한 구간 집합의 합집합을 취하는 효율적인 알고리즘을 찾고 있습니다.

미리 감사드립니다.

Answer 1

용어 중 하나 (예 : 시작)로 정렬 한 다음 목록을 이동할 때 해당 (오른쪽) 이웃과 중복되는지 확인하십시오. 내가하지 매우 확신

s=[tp(0,1),tp(0,3)] 

하지만 난이 올바른 방법이라고 생각 : 때

class tp(): 
    def __repr__(self): 
     return '(%d,%d)' % (self.start, self.end) 
    def __init__(self,start,end): 
     self.start=start 
     self.end=end 
s=[tp(5,10),tp(7,8),tp(0,5)] 
s.sort(key=lambda self: self.start) 
y=[ s[0] ] 
for x in s[1:]: 
    if y[-1].end < x.start: 
     y.append(x) 
    elif y[-1].end == x.start: 
     y[-1].end = x.end 

Answer 2

sweep line 알고리즘을 사용하십시오. 기본적으로 목록의 모든 값을 정렬합니다 (각 항목과 함께 간격의 시작 또는 끝 여부를 유지함). 이 연산은 O (n log n)입니다. 그런 다음 정렬 된 항목을 따라 단일 패스를 반복하고 간격 O (n)을 계산합니다.

O (N 로그 n) + O (N) = O이 (N 로그 n)

Answer 3

정렬 모든 점. 그런 다음 "시작"지점에 대한 카운터를 증가시키고 "끝"지점에 대해 감소시킵니다. 카운터가 0에 도달하면 실제로는 노조의 간격 중 하나의 끝점입니다.

카운터는 절대 음수가되지 않으며 목록 끝에 0이됩니다.

Answer 4

는 geocar에 의한 알고리즘은 실패

class tp(): 
    def __repr__(self): 
     return '(%.2f,%.2f)' % (self.start, self.end) 
    def __init__(self,start,end): 
     self.start=start 
     self.end=end 
s=[tp(0,1),tp(0,3),tp(4,5)] 
s.sort(key=lambda self: self.start) 
print s 
y=[ s[0] ] 
for x in s[1:]: 
    if y[-1].end < x.start: 
     y.append(x) 
    elif y[-1].end == x.start: 
     y[-1].end = x.end 
    if x.end > y[-1].end: 
     y[-1].end = x.end 
print y 

가 나는 또한 공제를 구현 :

#subtraction 
z=tp(1.5,5) #interval to be subtracted 
s=[tp(0,1),tp(0,3), tp(3,4),tp(4,6)] 

s.sort(key=lambda self: self.start) 
print s 
for x in s[:]: 
    if z.end < x.start: 
     break 
    elif z.start < x.start and z.end > x.start and z.end < x.end: 
     x.start=z.end 
    elif z.start < x.start and z.end > x.end: 
     s.remove(x) 
    elif z.start > x.start and z.end < x.end: 
     s.append(tp(x.start,z.start)) 
     s.append(tp(z.end,x.end)) 
     s.remove(x) 
    elif z.start > x.start and z.start < x.end and z.end > x.end: 
     x.end=z.start 
    elif z.start > x.end: 
     continue 

print s 

Answer 5

이 p http://en.wikipedia.org/wiki/Interval_tree, http://en.wikipedia.org/wiki/Segment_tree, 또한 'RangeTree'

(OP의 질문 간격의 큰 수를 포함 이러한 데이터 구조체 중요)

: 명칭 (들)에서가는 공상의 다양한 수준에서 - roblem은, 몇 번을 해결하고있다 파이썬 라이브러리 선택의 내 자신의 선택의 측면에서

---

:

테스트에서

• , 내가 찾는거야 모든 기능과 파이썬 현재이라는 측면에서 대부분의 손톱이 (비 비트 - 부패 무엇을 그) : ' SymPy의 'Interval'및 'Union'클래스는 다음을 참조하십시오. http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• 성능이 좋지만 기능이 풍부한 옵션 (예 : https://pypi.python.org/pypi/Banyan

마지막 : IntervalTree, SegmentTree, RangeTree의 어느 하나에, SO 자체에 주위를 검색하고 답변을 찾을/후크 더 풍부한 맛

Answer 6

점 범위 제거)를 떠 작동하지 않았다 C++ 단위의 합집합을 찾으려면

#include <iostream> 
#include <algorithm> 

struct interval 
{ 
    int m_start; 
    int m_end; 
}; 

int main() 
{ 
    interval arr[] = { { 9, 10 }, { 5, 9 }, { 3, 4 }, { 8, 11 } }; 

    std::sort(
     arr, 
     arr + sizeof(arr)/sizeof(interval), 
     [](const auto& i, const auto& j) { return i.m_start < j.m_start; }); 

    int total = 0; 
    auto current = arr[0]; 
    for (const auto& i : arr) 
    { 
     if (i.m_start >= current.m_end) 
     { 
      total += current.m_end - current.m_start; 
      current = i; 
     } 
     else if (i.m_end > current.m_end) 
     { 
      current.m_end = i.m_end; 
     } 
    } 

    total += current.m_end - current.m_start; 
    std::cout << total << std::endl; 
}