Związek interwałów

Question

Mam klasę reprezentującą interwał. Ta klasa ma dwie właściwości "start" i "koniec" porównywalnego typu. Teraz szukam skutecznego algorytmu, który pozwoli na połączenie zestawu takich interwałów.

Z góry dziękuję.

Answer 1

Posortuj je według jednego z haseł (na przykład start), a następnie sprawdź, czy nie zachodzą na siebie z sąsiednim (prawym) sąsiadem podczas poruszania się po liście.

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

Użyj algorytmu sweep line. Zasadniczo sortuje się wszystkie wartości na liście (przy zachowaniu, czy jest to początek, czy koniec przedziału wraz z każdym elementem). Ta operacja to O (n log n). Następnie pętla w jednym przebiegu wzdłuż posortowanych elementów i oblicz przedziały O (n).

O (n log n) + O (n) = O (n log n)

Answer 3

Sortowanie wszystkich punktów. Następnie przejrzyj listę zwiększającą licznik punktów startowych i zmniejszającą ją dla punktów końcowych. Jeśli licznik osiągnie 0, to naprawdę jest punktem końcowym jednego z przedziałów w unii.

Licznik nigdy nie będzie ujemny i osiągnie 0 na końcu listy.

Answer 4

Algorytm przez geocar zawiedzie, gdy:

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

nie jestem bardzo pewien, ale myślę, że to jest właściwa droga:

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 

ja również wprowadziły go do odejmowania:

#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

Okazuje się, że p ROBLEM został rozwiązany, wiele razy - na różnym poziomie fantazji, przechodząc pod nomenklatury (ów): http://en.wikipedia.org/wiki/Interval_tree, http://en.wikipedia.org/wiki/Segment_tree, a także „RangeTree”

(jak pytanie OP wiąże duże liczby przedziałów te datastructures znaczenia)

---

w kategoriach własnego wyboru selekcji biblioteki Pythona:

• z testów, jestem stwierdzenia, że ​​to, co większość paznokcie go w kategoriach bycia pełen prąd funkcjonalnym i python (non-bit zgnił): " Klasy "Interval" i "Union" od SymPy, patrz: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• Kolejny dobry wybór, lepsza wydajność, ale mniej funkcjonalna opcja (np. nie działa na zmiennoprzecinkowych usunięcie Zakres) https://pypi.python.org/pypi/Banyan

Wreszcie szukaj okolice na SO sobie, w ramach jakiegokolwiek drzewo przedziałowe, SegmentTree, RangeTree, a znajdziesz odpowiedź/haki dalej Galore

Answer 6

Aby znaleźć całkowity związek przedziałów w 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; 
}