간격의 연합

Question

간격을 나타내는 클래스가 있습니다. 이 클래스에는 비슷한 유형의 두 가지 속성 "start"및 "end"가 있습니다. 이제 저는 그러한 간격의 세트를 조합하기 위해 효율적인 알고리즘을 찾고 있습니다.

미리 감사드립니다.

Answer 1

용어 중 하나 (예 : 시작)로 정렬 한 다음 목록을 이동할 때 (오른쪽) 이웃과 겹치는지 확인하십시오.

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

사용 스윕 라인 연산. 기본적으로 모든 값을 목록에 정렬합니다 (각 항목과 함께 간격의 시작 또는 끝인지 여부를 유지하는 동안). 이 작업은 O (N log n)입니다. 그런 다음 정렬 된 항목을 따라 단일 패스로 루프하고 O (N) 간격을 계산합니다.

o (n log n) + o (n) = o (n log n)

Answer 3

이 문제는 여러 차례 해결되었으며, 다양한 수준의 공상으로 명명법 (들)에 따라 다루어졌다. http://en.wikipedia.org/wiki/interval_tree , http://en.wikipedia.org/wiki/segment_tree , 또한 'rangetree'

(OP의 질문은 이러한 데이터 구조가 중요합니다)

---

내 자신의 Python 라이브러리 선택 측면에서 :

• 테스트에서, 나는 대부분의 손톱이 전체 특집 및 파이썬 전류 (비트 롯트) : Sympy의 'Interval'및 'Union'클래스를 참조한다는 것을 알게되었습니다. http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• 또 다른 좋은 선택, 고급 성능이지만 기능이 적은 옵션 (예 : 부동 소수점 범위 제거에서는 작동하지 않음) : https://pypi.python.org/pypi/banyan

마지막으로 : Intervaltree, Segmenttree, Rangetree 아래에서 So 자체를 검색하면 답변/후크가 더 많이 찾을 수 있습니다.

Answer 4

Geocar의 알고리즘은 다음과 같은 경우에 실패합니다.

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

확실하지 않지만 이것이 올바른 방법이라고 생각합니다.

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

모든 점을 정렬하십시오. 그런 다음 "시작"포인트에 대한 카운터를 증가시키고 "종료"포인트로 줄이는 목록을 살펴 봅니다. 카운터가 0에 도달하면 실제로는 노조 간격 중 하나의 종점입니다.

카운터는 결코 음수가되지 않으며 목록 끝에서 0에 도달합니다.

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