Union der Intervalle

Question

Ich habe eine Klasse repräsentiert ein Intervall bekommt. Diese Klasse hat zwei Eigenschaften „Start“ und „Ende“ einen vergleichbaren Typs. Jetzt bin ich auf der Suche nach einem effizienten Algorithmus, um die Vereinigung einer Menge von solchen Intervallen zu nehmen.

Vielen Dank im Voraus.

Answer 1

sortieren sie durch eine der Bedingungen (Starts, zum Beispiel), dann für Überlappungen überprüfen mit seinem (rechten) Nachbarn, wie Sie durch die Liste zu gehen.

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

Mit dem Sweep Linie Algorithmus rel="nofollow. Grundsätzlich Sie sortieren alle Werte in einer Liste (unter Beibehaltung ob es zu Beginn oder Ende des Intervalls zusammen mit jedem Punkt). Diese Operation ist O (n log n). Dazu Schleife in einem einzigen Durchlauf entlang der sortierten Gegenstände und berechnet die Intervalle O (n).

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

Answer 3

Es stellt sich heraus, dieses Problem viele Male gelöst wurde - auf ein Niveau von Phantasie unterschiedlichen, unter Nomenklatur gehen (e): http://en.wikipedia.org/wiki/Interval_tree , http: //en.wikipedia.org/wiki/Segment_tree , und auch 'Bereichsbaum'

(als OP Frage große Zählungen von Intervallen beinhaltet diese Datenstrukturen Materie)

---

in Bezug auf meine eigenen Wahl der Python-Bibliothek Auswahl:

• Von Tests, ich finde das, was die meisten Nägel es in Bezug auf die voll funktionsfähigen und Python Strom (nicht Bit-verrottete) sein: das ‚Interval‘ und ‚Union‘ Klassen von SymPy finden Sie unter: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• Eine andere gut aussehende Wahl, eine höhere Leistung, aber weniger funktionsreiche Option (zB nicht funktioniert Punktbereich Entfernung zu schweben.): https://pypi.python.org/pypi/Banyan

Schließlich: Suche auf SO selbst um, unter einem IntervalTree, SegmentTree, Bereichsbaum, und Sie finden Antworten / Haken weiter in Hülle und Fülle

Answer 4

Der Algorithmus von geocar schlägt fehl, wenn:

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

Ich bin mir nicht ganz sicher, aber ich denke, das ist der richtige Weg ist:

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

Ich setze es auch für die Subtraktion:

#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

Sortieren Sie alle Punkte. Dann gehen Sie durch die Liste Erhöhen eines Zählers für „Start“ Punkte und Erniedrigen es für „Ende“ Punkte. Wenn der Zähler 0 erreicht, dann ist es wirklich ein Endpunkt eines des Intervalls in der Union.

Der Zähler wird niemals negativ werden, und wird 0 am Ende der Liste erreichen.

Answer 6

Um die Gesamt der Vereinigung der Intervalle in C ++ finden

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