Überlappende Bereiche, erhalten Sie einzigartige

Question

Ich habe eine Liste von Bereichen, zum Beispiel 0-100. Ich muss die einzigartigen Werte, die nur einmal auftreten, so schnell wie möglich erhalten.

Zum Beispiel reicht:

0 - 10 
5 - 20 
30 - 40 

0 - 10 (+11) sind einzigartig, keines dieser Zahlen kam vor

von 5 bis 10 sind nicht eindeutig, so zählen sie nicht.

11 - 20 (10) sind einzigartig, 30 - 40 (+11) zu

Auf diese Weise kehrt 32.

Irgendwelche Vorschläge?

Answer 1

>>> a = range(11) 
>>> b = range(5, 21) 
>>> c = range(30, 41) 
>>> set(i for i in a + b + c) 
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40]) 
>>> len(_) 
32 

Oder besser:

>>> from itertools import chain 
>>> a = xrange(11) 
>>> b = xrange(5, 21) 
>>> c = xrange(30, 41) 
>>> set(chain(a, b, c)) 

Und in Python 3:

>>> from itertools import chain 
>>> a = range(11) 
>>> b = range(5, 21) 
>>> c = range(30, 41) 
>>> set(chain(a, b, c)) 

Hoffe, es hilft!

Answer 2

In Ihrem Beispiel sind die Bereiche aufsteigend nach der unteren Grenze des Bereichs sortiert. Ich werde für diese Lösung annehmen, dass dies immer der Fall sein wird.

Grundsätzlich wäre es die Idee, die Bereiche zu durchlaufen und jeder Zählvariablen eindeutige Werte hinzuzufügen.

Um festzustellen, wo die eindeutigen Werte beginnen, vergleichen Sie, wo der vorherige Bereich endete, wo der neue Bereich beginnt.

Wenn die Untergrenze des neuen Bereichs kleiner als die alte Obergrenze ist, z. 0-10, dann 5-20, für Ihr Beispiel beginnen die eindeutigen Werte an der vorherigen oberen Grenze + 1 (dh die obere Grenze ist 10, die eindeutige beginnt bei 11). Wenn die neue obere Grenze kleiner als die alte obere Grenze ist, müssen keine neuen Werte hinzugefügt werden (z. B. 0-10, dann 2-7).

Wenn die neue untere Grenze größer ist als die alte obere Grenze (dh 5-20, 30-40), dann sind alle neuen Werte eindeutig.

Pseudo-Code:

var count = 0, lowerBound = 0, upperBound = 0; 
foreach range in ranges: 
    if range.lowerBound <= upperBound: 
     if range.upperBound < upperBound: 
     continue; 
     else: 
     lowerBound = upperBound + 1; 
    else: 
     lowerBound = range.lowerBound; 
    upperBound = range.upperBound; 
    count += upperBound - lowerBound + 1;