重疊範圍，得到唯一

Question

我有一個範圍列表，例如0-100。 我需要儘可能快地獲得僅出現一次的唯一值。

例如範圍：

0 - 10 
5 - 20 
30 - 40 

0 - 10（+11）是獨一無二的，沒有這些數字

5日前來到 - 10不是唯一的，所以不要指望他們。

11 - 20（+10）是獨一無二的，30 - 40（+11）太

這樣，它返回32

有什麼建議？

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 

或者更好：

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

而且在Python 3：

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

希望它能幫助！

Answer 2

在您的示例中，範圍按範圍的下限以升序排序。我會假設這個解決方案總是如此。

基本上，這個想法是遍歷範圍，每次添加一個計數變量的唯一值。

要確定唯一值的起始位置，請比較上一個範圍的結束位置和新範圍的起始位置。

如果新範圍的下限小於舊的上限，即， 0-10然後是5-20，根據你的例子，唯一值將從前面的上界+ 1開始（即上界是10，唯一從11開始）。如果新的上限小於舊的上限，則沒有要添加的新值（即，0-10，然後是2-7）。最後，如果新的下界大於舊的上界（即5-20然後30-40），則所有新值都是唯一的。

僞代碼：

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;