M. A. M. A. - 3 months ago 7
Python Question

Finding Missing Elements among a range of number lines

Let's say I have a list of ranges (ie.

[[1,100][102, 200], etc]]
. I want to find the number of missing elements in the total range. I have a working algorithm below:

def missing(numranges):
(minimum, maximum) = (min(map(lambda x: x[0], numranges)),
max(map(lambda x: x[1], numranges)))
(count, i) = (0, minimum)

while i < maximum:
if any(j <= i <= k for j, k in numranges):
count += 1
i += 1

return maximum - minimum - count


The problem is if you have say a number line that say is like
[[1, 10000], [10002, 20000]]
, then i goes over all 20,000 elements and it seems to me that this is very inefficient. I'm trying to find a way to make the algorithm better but I'm a bit stumped.

Edit: Sorry, should have mentioned that the number ranges could overlap (ie.
[1, 10000], [1, 100001], [100003, 100005], etc]]

Answer

See this code

l=[[1, 50], [55, 90], [95, 100]]
res=[]
for item in l :
    res.extend(range(item[0],item[1]))
print [k for k in range(max(res)) if k not in res]

Output :

[0, 50, 51, 52, 53, 54, 90, 91, 92, 93, 94]
Comments