Union des intervalles

Question

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

Merci d'avance.

Answer 1

Triez-les selon l'un des termes (début, par exemple), puis vérifiez les chevauchements avec son voisin (celui de 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 balayage . Fondamentalement, vous triez toutes les valeurs d'une liste (en conservant le début ou la fin de l'intervalle avec chaque élément). Cette opération est O (n log n). Ensuite, vous passez en boucle dans les éléments triés et calculez les intervalles O (n).

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

Answer 3

Il s'avère que ce problème a été résolu à maintes reprises - à différents niveaux de fantaisie, sous nomenclature (s): http://en.wikipedia.org/wiki/Interval_tree , http: //fr.wikipedia.org/wiki/Segment_tree , ainsi que 'RangeTree'

(comme la question de OP implique un grand nombre d'intervalles, ces infrastructures de données sont importantes)

en ce qui concerne mon choix de sélection de la bibliothèque python:

• D'après les tests, je constate que la plupart des choses la décrivent en termes de fonctionnalités complètes et de courant python (non-décomposé): les classes "Interval" et "Union" de SymPy, voir: http://sympystats.wordpress.com/2012/30/simplifying-sets/

• Un autre bon choix, une option plus performante mais moins riche en fonctionnalités (par exemple, ne fonctionnait pas avec la suppression de la plage à virgule flottante): https://pypi.python.org/pypi/Banyan

Enfin: recherchez autour de SO lui-même, sous l’un des IntervalTree, SegmentTree, RangeTree et vous obtiendrez des réponses / crochets encore plus loin

Answer 4

L'algorithme par géocar échoue lorsque:

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

Je ne suis pas très sûr mais je pense que c'est la bonne manière:

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 implémenté 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

Trier tous les points. Parcourez ensuite la liste en incrémentant un compteur pour " start " pointe et décrémente-le pour " fin " points. Si le compteur atteint 0, il s'agit en réalité d'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 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;
}