Union d'intervalles

Question

J'ai une classe représentant un intervalle. Cette classe a deux propriétés "start" et "end" d'un type comparable. Maintenant, je cherche un algorithme efficace pour prendre l'union d'un ensemble de tels intervalles.

Merci d'avance.

Answer 1

Triez-les selon l'un des termes (début, par exemple), puis vérifiez les chevauchements avec leur voisin (main droite) lorsque vous vous déplacez dans la liste.

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

Utilisez l'algorithme sweep line. Fondamentalement, vous trier toutes les valeurs dans une liste (tout en gardant le début ou la fin de l'intervalle avec chaque élément). Cette opération est O (n log n). Ensuite, vous bouclez un seul passage le long des éléments triés et calculez les intervalles O (n).

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

Answer 3

Trier tous les points. Ensuite, parcourez la liste en incrémentant un compteur pour les points de "départ", et en le décrémentant pour les points de "fin". Si le compteur atteint 0, alors c'est vraiment un point final de l'un des intervalles de l'union.

Le compteur ne deviendra jamais négatif et atteindra 0 à la fin de la liste.

Answer 4

L'algorithme par geocar échoue lorsque:

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

Je ne suis pas très sûr, mais je pense que cela est la bonne façon:

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 

Je l'ai également mis en œuvre pour la soustraction:

#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

Il s'avère que ce p roblème a été résolu, plusieurs fois plus - à différents niveaux de fantaisie, en passant sous la nomenclature (s): http://en.wikipedia.org/wiki/Interval_tree, http://en.wikipedia.org/wiki/Segment_tree, et aussi « RangeTree »

(comme la question de l'OP implique un grand nombre d'intervalles ces datastructures importance)

---

en termes de mon propre choix de sélection de bibliothèque python:

• de test, je trouve que ce que la plupart des clous en termes d'être complet et actuel python (non binaire pourris) : la ' Interval 'et' Union 'classes de SymPy, voir: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• Un autre bon choix, une performance plus élevée, mais moins caractéristique riche en fonctionnalités (par exemple. ne fonctionne pas sur le retrait de la plage à virgule flottante): https://pypi.python.org/pypi/Banyan

Enfin: une recherche sur elle-même SO, en vertu des IntervalTree, SegmentTree, RangeTree, et vous trouverez des réponses/crochets plus à gogo

Answer 6

Pour trouver le total de l'union des intervalles en 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; 
}