M. A. - 1 year ago 79
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]]`

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]
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download