0

I have a range from say 1013 to 20798654. I have a queue of ranges that I am working my way through. What I want is a collection of ranges that make up the space that the ranges from the queue don't cover. So for example above if I had just two new ranges coming in [1017, 1100] and [1000000,1500000] then I would want a set of ranges like [[1013,1017],[1100,1000000],[1500000,20798654]].

Does anyone know of an efficient way of doing this? The main range is in the region of 6Bn wide and we have around 170m ranges in the queue.

user3521296
  • 1
  • 1
  • It's this sort of thing: http://stackoverflow.com/questions/6017523/how-to-combine-overlapping-time-ranges-time-ranges-union – ajm475du Apr 10 '14 at 22:12
  • Sort your ranges first, then iterate through them - the start of each range will be the end of a gap and vice versa. – Dawood ibn Kareem Apr 10 '14 at 22:12
  • I have tried sorting the ranges and that does work but it is expensive when I have so many of them. – user3521296 Apr 10 '14 at 22:17
  • 3
    How many intervals do you expect in the output? Since you know your ranges, you could approach it the other way around: start with the full range as empty interval (`[0, 6Bn]`) and 'cut out' the other intervals one by one. Your result is sorted by definition, so you can do a binary search there. I guess this runs in `O(n log k)`, where `k` is the number of empty intervals (throughout the algorithm, not necessarily at the end). If `k << n`, this might be slightly faster than sorting the input. – Vincent van der Weele Apr 10 '14 at 22:32
  • By the way, is it really that much work to write out billion and million? At least, that's how I interpret Bn and m, but maybe you were referring to bunnies and mice. – Vincent van der Weele Apr 10 '14 at 22:33
  • are your non-gaps ranges tight packed or not ? ... to be clear 1,2,3,5,6 means that 4 is gap range or not ? have no clue for what purpose you do this but limiting the minimal gap size or min non gap density could take away much of the ranges ... according to input data of course. PS 170m means 170 Mega (*10^6) because I am used to SI and m means 10^-3 !!! – Spektre Apr 11 '14 at 12:01

0 Answers0